0
4

1 に答える 1

3

チューリングマシン

まず、チューリング マシンとは何かを理解する必要があります。チューリング マシンとは、ユニバーサル チューリング マシンについて話していることを前提としています。これは、コンピューター サイエンスのゴッドファーザーであるアラン チューリングによって作成された概念的なマシンです。

マシンはいくつかのコンポーネントで構成されています。まず、入力を含む無限のテープ。何かのようなもの..

1-0-1-1-1-1-0-1-0-1-0

それから一連のルール..

if 1 then 0
if 0 then 1

したがって、マシンが にヒットすると、ルールに従って、1出力はになります。読み取りヘッドが設定されたときに値をヒット0するマシンを定義します。読み取りヘッドは、チューリング マシンの現在位置のようなものです。それで行きます..

1-0-1-1
^------------Current head.

次に、次の反復:

1-0-1-1
  ^----------Current Head

このマシンは、実際にはビットごとの機能をシミュレートしていNOTます。チューリング マシンで状態を設定することもできます。たとえば、次のようになります。

if 1 then enter state 1
if 0 then enter state 0

大したことですよね？たとえば、突然、次のようなことができるようになりました。

1. if 1 and in state 1 output 1 and enter state 0
2. if 1 and in state 0 output 0 and enter state 1
3. if 0 and in state 0 output 1 and enter state 1
4. if 0 and in state 1 output 0 and enter state 0

そして、状態をデフォルト状態として定義します。この例では、 と呼びましょうstate 0。そのため、マシンが起動すると、1 が表示されます。これで、ルール番号state 0が取得された1ので、ルール番号を実行します2。a を出力して0と入力しstate 1ます。次の番号は0です。さて、私は にいるstate 1ので、ルール番号 を呼び出します4。これがどこに向かっているのかわかりますか？状態を追加することで、できることが本当に広がります。

現在、ユニバーサル チューリング マシンは、チューリング完全として知られているものです。これは、計算可能なシーケンスを計算できることを意味します。あなたの課題の仕様を含む！

あなたの課題

それでは、チューリング マシンのコンテキストで割り当てを見てみましょう。

機械の目的は、印刷することです..

0 1 00 01 11 000 001 011 111

したがって、状態を維持する必要があることがわかります。また、状態がますます深くなる必要があることもわかっています。したがって、ユーザーが を入力した場合000、出力する文字が 3 つあることを知る必要があります。

宿題の手伝いに関しては、残念ながら私が責任を持ってあなたに与えなければならないのはそれだけです. チューリング マシンを十分に理解し、さらにチューリング マシンが何をする必要があるかを理解することで、解決策の研究が始まります。

于 2015-04-05T23:52:35.023 に答える