Как создать машину Тьюринга, которая служит калькулятором функций для 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 повторно

возведите в квадрат число на ленте - x ^ 2 вычисляется путем помещения x на ленту и умножения его на себя

(последний шаг) увеличьте число на ленте до значения другого номера на ленте - это можно сделать, выполнив шаг 2 повторно

Чтобы выполнить задание несколько раз N раз, поместите N на ленту, выполните задание один раз, затем вычтите 1 из конца числа N. Повторяйте, пока число N не исчезнет с ленты.

Надеюсь, этого достаточно для начала. Таким образом, конечный автомат может быть построен более или менее механически.

Answer 2

В моем собственном псевдокоде Тьюринга:

1. скопируйте входные данные A0B на ленту 2
2. запишите 000010000 на ленту 3
   • умножьте число на ленте 3 на А, полученное из ленты 2, на
     1. начиная с начала
     2. запись 0 на ленту 4
        • число копирования 3 => 4
        • перемещение вперед один раз на ленте 3 (3++)
        • переходим к шагу 3, пока A не закончится
        • перенос ответа с ленты 4 на ленту 3
   • уменьшите число B на ленте 2
3. Если B на ленте 2 не равно 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
#                          ^

Пожалуйста, проверьте, нет ли ошибок :)