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

Все в мире можно запрограммировать (создать алгоритм) из предельно простых операций (запись символа, стирание, сдвиг головки) и 0,1.

Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста и нормальным алгорифмам Маркова.http://kpolyakov.spb.ru/prog/turing.htm

Согласно тезису Поста, любой алгоритм может быть записан в виде программы для машины Поста. Доказано, что машина Поста по своим возможностям эквивалентна машине Тьюринга и нормальным алгорифмам Маркова.http://kpolyakov.spb.ru/prog/post.htm

https://deep-econom.livejournal.com/56644.html