x ^ yの関数電卓として機能するチューリングマシンの作成方法

StackOverflow https://stackoverflow.com/questions/1030203

  •  06-07-2019
  •  | 
  •  

質問

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

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を配置するにはどうすればよいですか？ （マルチテープマシンでもかまいません） 状態図はどのように見えますか？

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

だから：

   0 = delimiter
   1 =    0
   11 =   1
   111 =  2
   1111=  3
   11111= 4 
   etc.
役に立ちましたか？

解決

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

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

タスクをN回繰り返し実行するには、Nをテープに貼り付け、タスクを1回実行してから、数字Nの末尾から1を引きます。数字Nがテープからなくなるまで繰り返します。

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

他のヒント

私自身のチューリング擬似コード：

  1. 入力A0Bをテープ2にコピー
  2. テープ3に000010000を書き込む
    • テープ3の数にテープ2のAを掛ける
      1. Aの先頭から開始
      2. テープ4に0を書き込む
        • コピー番号3 = gt; 4
        • テープ3（3 ++）で1回進む
        • 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
#                          ^

エラーを確認してください：）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top