Машина Тьюринга. Машина Поста.

[deep_econom]

Можно скачать проги и поиграть. Рекомендую

Comments

[bluxer]

Хочу разобраться в этой штуке, но не знаю даже, как ей дать задание решить 2+2=?

[deep_econom]

там в каталоге EXAMPLES есть примеры
в частности файл "adddec.tur"
где осуществляется сложение двух десятичных чисел

но это сложная программа, надо начинать с весьма простых

например для баловства я написал такую проги
1. найти первый символ справа от каретки и установить каретку на символ

[deep_econom]

типовые задачи простые
http://lpcs.math.msu.su/vml2008/t5turing.pdf

Задача 1. Заменить во входном слове из 0 и 1 все буквы 0 на 1 и наоборот.
Решение.
q1 # 7→ q2 # R
q2 0 7→ q2 1 R
q2 1 7→ q2 0 R
q2 # 7→ q0 # L
Задача 2. Переместить 0 через блок единиц (#011 . . . 1# ❀ #11 . . . 10#).
Решение.
q1 # 7→ q2 # R
q2 0 7→ q2 # R
q2 1 7→ q2 1 R
q2 # 7→ q0 0 L

[deep_econom]

гуглится pdf-файл
Решение задач МГУ Машина Тьюринга и алгоритмы Маркова

тут все подробно от простого к сложному

Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач.

а вот на ютубе в точности на этой программе пояснение

Машина Тьюринга. Введение. Понятие машины тьюринга. Решение задачи
Zimins RV&E
https://www.youtube.com/watch?v=clrdEuTX9r8
https://www.youtube.com/watch?v=1pyrb01JKKM