turing-machines - チューリングマシン命令表

Question

チューリング マシンの定義では、命令表 (プログラム) を読み取り/変更することは禁止されています。まさに、チューリング マシンはそれ自身のプログラムにアクセスできません。

この制限を弱めることができれば、どのような利点が得られるでしょうか? マシンがそのプログラムを分析および/または変更できる場合。それは、チューリング計算可能なタスクのクラスを拡張しますか?

Answer 1

チューリング マシンは既に別のチューリング マシンを実装しており、そのルールを変更して、たとえば修正可能なプログラムを入力として受け取ることができます。特に、チューリング マシンは計算可能なあらゆる関数を計算できます。理論的には、マクロや「自己変更」コードなどを持つLispインタープリターを実装できます。

したがって、答えはNOです。覚えておいてほしいのは、チューリング マシンを実際に欲しがった人はどこにもいないということです。（認めませんが、学部生としてそのようなことをしたかもしれません...） それは、さまざまな重要な証拠に基づいているだけです.

Answer 2

より完全に：「ユニバーサルチューリングマシン」と「チューリング「マシン」には違いがあります。通常のチューリングマシンにはハードワイヤードのルールセットがあるため、自己変更することはできません。あなたが説明したのはユニバーサルチューリングマシンです。これは、I/O に使用するのと同じテープからルールセットを読み取り、そのルールセットを変更する機能を備えています。UTM に、テープから変更されたルールセットをリロード (再起動) する機能がある場合、実際にはすでに自己です。 -変更。