無限のアルファベットチューリングマシン

Question

無限のアルファベットから記号を読み書きできるチューリングマシンは、通常のTMよりも強力です（つまり、マシンにはまだ有限数の状態があります）？

各シンボルを区別するために無限の数の状態が必要であるため、直感は私にそうではありません。したがって、シンボルまたはシンボル（または遷移の一部のサブセット）によって引き起こされる遷移のいくつかは同等でなければならないと思います。そのため、通常のTMとそのようなシンボルまたは遷移の境界付きサブセットを使用して、そのようなマシンを実際にシミュレートできます。

これの正式な証拠にどのようにアプローチできますか？

Answer 1

いいえ、それはより強力です。遷移関数はもはや有限ではなく、 それ あなたにたくさんの力を買います。

無限のアルファベットを使用すると、1つのシンボルの無限セットから入力アイテムをエンコードできます（ただし、入力セットはアルファベットセットよりも「無限」にすることはできません。実数のようなセットは、1つのシンボルで表すことができません）。同様に出力用。

したがって、2つの状態（1つの初期、1つは、1つの初期）を作成して、計算しようとしている関数に従って、状態を受け入れ、テープヘッドの下のシンボルを変更する単一の遷移で無限α-TMを作成できます。このレシピを使用すると、アルファベットと1対1の対応できるセット間のマッピングを計算できます。

したがって、その退化した種類のマシンがすべてに対する答えであることを避けるために、遷移関数ができることを制限する必要があります。明らかなのは、遷移関数自体が計算可能であることを要求することです（通常のTMの遷移関数は、有限であるため、結局は些細なことです）。しかし、その後、計算可能な関数を使用して、計算可能な関数のモデルを定義しようとするでしょう。

Answer 2

上記の答えは正しいですが、無限のアルファベットと計算可能性について言えることがもう少しあります。

チューリングマシンは、$ m =（q、 gamma、b、 sigma、 delta、q_0、q_f）$として$ m =（q、 gamma、b、 sigma、q_f）として説明されています。したがって、遷移関数$$ delta：q / f times gamma rightarrow q times gamma times {l、r } $$は必然的に有限です。

無限のアルファベットマシンでは、入力アルファベット$ sigma $を$ sigma^{inf} $に置き換えます。 } $遵守：

$$ delta^{inf}：q / f times gamma^{inf} rightarrow q times gamma^{inf} times {l、r } $$

したがって、$ delta^{inf} $は必然的に無限の関数です。この関数がコンポッツできない場合に言及したように、上記は有限ではありません。可能であれば、$ delta^{inf} $（partial）再帰的なものを保持すると仮定します。問題は、アルファベットが常にこれを許可するかどうかです。

基本的な問題は、有限のアルファベットが完全に提示されていることです（したがって、関数を再帰的に定義することを選択できます）が、無限のアルファベットを完全に提示することはできません。それでは、どのメカニズムがアルファベットを生成していますか？

これを考慮する最も簡単な方法は、有限の「コア」アルファベットがあると想像することです。次に、言語$ l subset a^*$を生成します。その文字列を想定します abaab $ in l $。次に、$ alpha =を定義しますu003Cabaab> in gamma^{inf} $。したがって、無限のアルファベットは、$ l $からの文字列のセットで構成されています。 独身 $のようなシンボルu003Cabaab>$。

最も単純なそのようなアルファベットは基本的にです <1*>, 、各シンボルの垂直ストロークの数をカウントすることにより、2つの記号が区別される通常の言語。これは、有限状態パーサー（ただし、LBAとして、有限のオートマトンとしてではなく）で計算可能です。チューリングは、TM操作における無限操作の出現を避けるために、有限のアルファベットを主張しました。ただし、英語のアルファベットの26文字は、このカウントパターンに従っていないことは注目に値します。文字Zには26のストロークやドットなどが含まれていません。したがって、再帰的に列挙可能な（再）言語$ l $に基づく最も一般的な計算パターンでは、他のパターンが可能です。

ただし、ここでの問題は、$ delta^{inf} $の構築は、$ l $の定義が明示的に提供されない限り、不可能であることです。これは、REセットの等価性が決定不可能であるためであり、それ以外の場合は、作業するための有限サンプルしか持っておらず、そこから$ l $を推測できないためです。 もしも $ l $（したがって$ gamma^{inf} $）の定義があります。 f $は絶対に再帰的であり、$ delta^{inf} $は再帰的です。

最後に、$ l $が2つの例を挙げていない場合を検討します。

例1. 。 $u003Cn> in gamma^{inf} $ iff $ phi_ {n}（n）$ $は、実証的に分岐します。この場合、アルファベット$ gamma^{inf} $は明らかに有限の説明を持っていません - 代わりに、それは時間の経過とともに「成長」します（そして、ある程度の計算制限でのみ完全に定義されます）。しかし、それはいかなる場合でも一度に提示することはできない無限のアルファベットです。したがって、$ f $が$ gamma^{inf} $で再帰的である場合、fは$ delta_2^0 $ - 停止セットになります。したがって、$ delta^{inf} $は再帰的ではありません。

例2. 。より幾何学的な例は、ペンローズのようなものを考慮します タイル. 。 $ s $が平面を確実にタイルできるn周期タイルの単位である場合、シンボル$ s in gamma^{inf} $とします。このアルファベットは、任意のNでペンローズタイルのNタイル単位を構築できるため、無限です。ただし、飛行機自体をタイリングできないため、このようなタイルがより多く発見されるにつれてSのセットが成長します。 $ gamma^{inf} $の$ f $再帰の可能性がありますが、絶対に再帰的ではないかもしれません。