如何创建一个图灵机作为 x^y 的函数计算器

Question

我正在学习图灵机测试，我遇到了一个问题，我必须创建一个图灵机作为函数计算器：

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.

Answer 1

我在这里猜测了一下，自从我玩图灵机模拟器以来已经有一段时间了。 首先，我想将任务分为几个概念步骤：

1. 将磁带上的数字增加到磁带上另一个数字的值
2. ，将磁带上的数字乘以磁带上另一个数字的值 - 这可以通过重复执行步骤 1 来完成
3. 磁带上的一个数字的平方 - x ^ 2 的计算方法是将 x 放在磁带上，然后将其与其自身相乘
4. （最后一步）将磁带上的一个数字乘以另一个数字的值磁带上的数字 - 这可以通过重复执行步骤 2 来完成。

要重复执行某项任务 N 次，请将 N 放入磁带上，执行该任务一次，然后从数字 N 的末尾减 1。重复，直到数字 N 为从磁带上消失了。

无论如何，希望这足以让您开始。 状态机可以或多或少以这种方式机械地构造。

Answer 2

在我自己的图灵伪代码中：

1. 将输入 A0B 复制到磁带 2
2. 将 000010000 写入磁带 3
   • 将磁带 3 上的数字乘以磁带 2 中的 A
     1. 从A开头开始
     2. 将 0 写入磁带 4
        • 复制数字 3 => 4
        • 在磁带 3 上前进一次 (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
#                          ^

请检查是否有错误:)