turing-machines - チューリングマシンがこの言語を決定するために必要な州はいくつありますか？

Question

言語L={1 ^ 200}、またはむしろ、200個の1が連続するような言語？別名、このTMは、200個の「1」を連続して受信した場合にのみ受け入れます。したがって、これを解決するには200の状態が必要でしょうか、それともより少ない状態で単純化できるでしょうか。

TMがどのように機能するかを理解するのに役立つようにこれを求めています。

注：アルファベットは{1}になります。TMは、必要な数のテープを使用できます。

Answer 1

L には単一の文 1^200 のみが含まれていると仮定します。次に、それはすべて、アルファベットとして何を定義するかによって異なります。「1」をアルファベットとして定義すると、初期状態を含めて 201 個の状態が必要になります。文字列 1^200 を「alphabet」として定義した場合、1^200 というラベルの付いた矢印で接続された初期状態と終了状態の 2 つの状態のみが必要になります。

Answer 2

決定論的な有限オートマトンの場合、@sawa が言ったように 201 個の状態が必要になります。ただし、チューリング マシンは、カウンターを保持し、それを 200 と比較できる場合があります。これは、より少ない状態で実行できます。必要な状態の数は、チューリング マシンのモデルによって異なります。マルチテープ マシンではおそらくより少ない状態を使用できますが、1 テープ マシンではおそらく 201 が必要になります。

Answer 3

2 つのテープ、または単純な {1,blank} よりも大きなテープ アルファベット (入力アルファベットとは異なる) を使用すると、はるかに優れた結果が得られます。実際、2 番目のテープまたは拡張アルファベットが必要なのは、入力の開始位置と終了位置をマークするためだけです。

したがって、次のように開始できます。1 つおきに入力を消去します。同時に、入力の長さのパリティをカウントできます。これは、EVEN と ODD と呼ばれる 2 つの状態だけで実行できます。EVEN 状態で開始します。1 を読み取ると、ODD 状態に切り替わります。ODD 状態で 1 を読み取ったら、それを消去して EVEN 状態に切り替えます。

次に、さらに 2 つの状態を使用して同じことを行います。次に、さらに 2 つの状態で 3 回目の入力を調べます。この時点で、スイープの 1 つが奇数の 1 を読み取ったときにマシンが拒否したか、1 の数が 1/8 になりました。

同様の構成を使用して、5 つの 1 ごとに 4 つを消去し、入力の長さが 5 の倍数であることを確認して、入力を実行できます。これは 5 つの状態で実行できます。それを2回行います。

ここで、すべてのパリティ チェックと (5 アリティ) チェックに合格し、単一の 1 が残っている場合、元の入力には 1*5*5*2*2*2=200 個の 1 が含まれています。そうでなければそうではありません。使用される状態の合計: 2+2+2+5+5=16 (または、受け入れ状態と拒否状態を数える場合は 18)。

より洗練された構造は、より少ない状態で同じタスクを実行できますが、ランタイムがばかげていることはほぼ保証されており、少なくとも {0,1,blank} のテープ アルファベットが必要になります。チューリング マシンがどのように機能するかを本当に理解したい場合は、アルゴリズムがチューリング マシンのランダム アクセス メモリ (状態の形式) の不足をどのように補うかについて考えてみてください。言語 {1^99} 用に同様のアルゴリズムを作成できますか? {1^97} はどうでしょうか (ヒント: 97 個未満の状態でも実行できますが、新しい賢さが必要になります)。