2

チューリングマシンのテストを勉強していますが、次の関数計算機として機能するチューリングマシンを作成する必要があるという問題に悩まされています。

f(x,y) = x ^ y

テープ入力が次のように分離されることを理解しています。

1's of base 0 1's of exponent

私のテープ出力は

1's of base 0 1's of exponent 0 1's of the computed result

XとYをテープに配置するにはどうすればよいですか？（マルチテープマシンの場合もあります）状態図はどのようになりますか？

注：私は単項を使用しており、1は0を表すために使用され、0は値としてではなく区切り文字として使用されます。

それで：

   0 = delimiter
   1 =    0
   11 =   1
   111 =  2
   1111=  3
   11111= 4 
   etc.
4

2 に答える 2

4

ここで少し推測しますが、チューリングマシンのシミュレーターで遊んでから少し経ちました。まず、タスクをいくつかの概念的なステップに分割したいと思います。

  1. テープ上の別の番号の値だけテープ上の番号をインクリメントします
  2. テープ上の数値にテープ上の別の数値の値を掛けます-これは、ステップ1を繰り返し実行することで実行できます。
  3. テープ上の数を二乗する-x^2は、テープにxを置き、それをそれ自体で乗算することによって計算されます。
  4. （最後のステップ）テープ上の数値をテープ上の別の数値の累乗に上げる-これは、ステップ2を繰り返し実行することで実行できます。

タスクをN回繰り返し実行するには、テープにNを入れ、タスクを1回実行してから、番号Nの末尾から1を引きます。番号Nがテープからなくなるまで繰り返します。

うまくいけば、これはとにかく始めるのに十分です。ステートマシンは、この方法で多かれ少なかれ機械的に構築できます。

于 2009-06-23T01:47:16.990 に答える
1

私自身の Turing 疑似コードでは:

  1. 入力 A0B をテープ 2 にコピー
  2. 000010000 をテープ 3 に書き込みます
    • テープ 3 の数字にテープ 2 の A を掛けます。
      1. Aの先頭から
      2. テープ 4 に 0 を書き込みます
        • コピー番号 3 => 4
        • テープ 3 で 1 回進む (3++)
        • A が終了しない限り、ステップ 3 に進みます
        • 回答をテープ 4 からテープ 3 に移動します
    • テープ 2 の番号 B を減らす
  3. テープ 2 の B が 0 でない場合は、手順 2 に進みます。
  4. テープ 3 の答えをテープ 1 にコピーします

動作するチューリング コードは次のとおりです (テープはポインターのようなもので、小文字、入力テープは ですi)。


# At the start for 2^3
# i: 000111011110000
#       ^

_start_ -> *a = 0, start2
start2 [*i==0] -> i++, *a++ = 0, *b++ = 0, start4
start2 [*i==1] -> i++, *a++ = 1, start2
start4 [*i==0] -> *b-- = 0, b--, initc
start4 [*i==1] -> i++, *b++ = 1, start4
initc -> *c++ = 0, *c++ = 1, *c++ = 1, *c-- = 0, mult

# example
# i: 00011101111000
#              ^
# a: 001110000
#        ^
# b: 001111000
#         ^
# c: 00011000
#        ^

mult[*b==0]: lastcpy
mult[*b==1]: b--, *d++ = 0, *d++ = 1, rewa
rewa[*a==0]: a++, a++, multcpy
rewa[*a==1]: a--, rewa

multcpy[*c==1]: c++, multcpy2
multcpy[*c==0]: multcpy3
multcpy2[*a==0]: multcpy
multcpy2[*a==1]: *d++ = 1, multcpy2
multcpy3: *d-- = 0, *c = 0, cpydtoc

cpydtoc[*d==1]: d--, *c++ = 1, cpydtoc
cpydtoc[*d==0]: *c-- = 0, mult

lastcpy[*c==1]: *i++ = 1, c--, lastcpy
lastcpy[*c==0]: *i = 0, _finish_

# Should end with
# i: 00011101111011111111100
#                          ^

エラーがないか確認してください:)

于 2009-06-23T01:55:02.903 に答える