mapping - 有限チューリングマシンでの自然で認識可能な言語のマッピング

Question

私はこの理論的な質問に対する答えを見つけるのに苦労してきました。それが直接プログラミングの質問ではない場合でも、それは本当に関連していると思います。

1000平方を超えることのできないチューリングマシンのタイプを想定します。そのようなタイプの認識可能な言語のセットと通常の認識可能な言語のセットとの間の関係は何でしょうか。

Answer 1

私があなたの質問を正しく理解しているなら、あなたは最終的なアルファベットのいくつかの一定の長さ（あなたの質問では1000）の要素に制限されているテープを備えたチューリングのようなマシンについて話している。テープの長さは入力サイズに依存しません（線形拘束オートマトンの場合）。

• このシナリオでは、テープで表すことができる状態の数は一定です。より具体的には、テープの長さがTで、アルファベットのサイズがAの場合、テープは^AT状態のみをエンコードできます。

• さらに、チューリングマシンにはいくつかの内部状態があります（これらの状態の数がSであるとしましょう）。各ポイントで、マシンにはテープの内部状態と状態があるため、通常の有限状態マシンを使用して、一定長のテープでチューリングマシンをシミュレートできます。

• 有限状態マシンを構築するには、制限されたチューリングマシンのすべての可能な状態を取得する必要があります。これは、マシンの内部状態（S個あります）とテープの状態（A ^T個）の組み合わせであるため、 S * ^AT状態の有限状態マシンになります。それはかなりたくさんありますが、理論的には気にしません-それは定数です。

だから、私の答えは、あなたの限られたコンスタントテープチューリングマシンは、有限状態マシンと同じ言語を認識できるということです。

Answer 2

あなたが説明していることは、チューリングマシンよりも線形拘束オートマトンに近いと思います。LBAは、状況依存言語を認識できます。

Answer 3

直感的には、限られたマシンでチューリング認識可能な言語の厳密なサブセットを認識できると思います。それを証明するには、言語を認識する最も効率的なチューリングマシンがテープ上に1000以上の位置を必要とするように、チューリング認識可能な言語を構築する必要があります。

Answer 4

定義上、無限ではないテープ（無限の値が適度に小さい場合）を備えた「チューリングマシン」は「チューリングマシン」ではありません。

実際には、そのような限られたマシンは、関心のある関数を計算するのに苦労するでしょう。