如何创建用作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和磁带上的数字来完成-x^2的计算方法是将x放在磁带上，然后将其与自身相乘
3. (最后一步)将磁带上的数字乘以磁带上另一个数字的值的幂-这可以通过重复执行步骤2

来完成

要将一个任务重复执行N次，请将N放到磁带上，执行一次该任务，然后从数字N的末尾减去1。重复此操作，直到数字N从磁带中消失。

希望这足以让你入门。状态机可以或多或少地以这种方式机械地构建。

Answer 2

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

1. copy input A0B to Tape 2
2. write 000010000 to Tape 3
   • 使用
     1. 将磁带3上的数字乘以磁带2中的A<

     >H19将0写入磁带4

     • 复制数字3 => 4
     • 在磁带3(3++)上向前移动一次
     • 除非A结束
     • 将答案从磁带4移动到磁带3

​

​

- decrement the number B on Tape 2 

​

1. 如果磁带2上的B不是0，请转到步骤2
2. 将答案从磁带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
#                          ^

请检查错误:)