@kuzy000 Блджад, разве не очевидно? Ну смотри. Есть у тебя кусок памяти, на ней конечное число битиков. Есть функция, набор правил, который к битикам применяется. Предполагаем, что функция эта, принимая на вход набор битиков, возвращает новый набор битиков Т.е. получаем функцию bitarray = foo(bitarray); Учитывая что количество битиков у нас конечно и не может вылезти за пределы, число состояний системы конечно т.е. в какой-то момент система повторит свое состояние. Сами состояния можно записать в виде направленного графа, который может выглядеть так, как показано на рисунке https://i.imgur.com/RX2nSvo.jpg Скомпилируй мою программу, посмотри как там происходят переходы состояний и как оно в итоге приходит к равновесию и скачет около чего-то. Так вот, мы по сути берем строку конечного размера (в нее входит набор правил, применяемый к битикам и само начальное состояние этих самых битиков же ) и на выходе получаем ГРАФ ПЕРЕХОДОВ ИЗ СОСТОЯНИЯ В СОСТОЯНИЕ. Это штука конечной длинны. А теперь конечный автомат. В него мы передаем тоже некие байтики, и там тоже есть некий набор правил, который делает с этими байтиками что-то такое осмысленное, и.. меняется, у нас получается полная аналогия. Например, есть Conway's Game of Life, знаешь? На ограниченном игровом поле это конечный автомат, и можно аналогично построить граф состояний игрового поля. Если в игре жизнь у нас конечное игровое поле, из состояния A однозначно следует состояние Б, из состояния Б однозначно следует состояние В, и так по цепочке система эволюционирует, пока не ЗАЦИКЛИТСЯ, а зациклится она неизбежно, игровое поле конечно. Ну и на Машине Тьюринга вполне можно создать конечный автомат(ту же игру жизнь), а сам процессор/микроконтроллер/этц с конечной памятью, регистрами и оперативкой, если в нем нет случайностей - это по своей сути есть ни что иное, как конечный автомат. Ясно? Между тем, доказано что игра "Жизнь" является полной по Тьюрингу, если происходит на бесконечном игровом поле