Как создать машину Тьюринга, которая служит калькулятором функций для x ^ y
-
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 на ленте (лентах)?(Это может быть магнитофон с несколькими кассетами) Как бы выглядела диаграмма состояний?
Примечание:Я использую унарный код, где 1 используется для представления 0, а 0 используется не как значение, а как разделитель.
Итак:
0 = delimiter
1 = 0
11 = 1
111 = 2
1111= 3
11111= 4
etc.
Решение
Я немного догадываюсь, прошло немного времени с тех пор, как я играл с симуляторами машин Тьюринга. Прежде всего, я хотел бы разделить задачу на несколько концептуальных шагов:
<Ол>Чтобы выполнить задание несколько раз N раз, поместите N на ленту, выполните задание один раз, затем вычтите 1 из конца числа N. Повторяйте, пока число N не исчезнет с ленты.
Надеюсь, этого достаточно для начала. Таким образом, конечный автомат может быть построен более или менее механически.
Другие советы
В моем собственном псевдокоде Тьюринга:
- скопируйте входные данные A0B на ленту 2
- запишите 000010000 на ленту 3
- умножьте число на ленте 3 на А, полученное из ленты 2, на
- начиная с начала
- запись 0 на ленту 4
- число копирования 3 => 4
- перемещение вперед один раз на ленте 3 (3++)
- переходим к шагу 3, пока A не закончится
- перенос ответа с ленты 4 на ленту 3
- уменьшите число B на ленте 2
- умножьте число на ленте 3 на А, полученное из ленты 2, на
- Если B на ленте 2 не равно 0, перейдите к шагу 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
# ^
Пожалуйста, проверьте, нет ли ошибок :)