Это реализация Машины Тьюринга. Зачем в таком виде - для прикола видимо.
Кроме всего прочего решаемость с помощью Машины Тьюринга является критерием решаемости задачи алгоритмически.
Простейший двоичный компьютер. Бесконечная (в теории) лента с нулями е единицами - программой, устройством считывания и записи и базовой логикой взаимодействия с этим всем.
МТ есть прототип, послуживший основой для современной вычислительной техники. Работает с данными, записанными на ленте. Имеет набор заранее запрограммированных внутренних состояний.
Для каждой пары состояние + символ на ленте определяется действие - сдвиг ленты вправо/влево, запись символа или переход в другое состояние.
Многим теориям вычислительной математики удобно работать именно с машиной Тьюринга или её эквивалентом. Поэтому когда мы говорим "вычислимо" - мы имеем в виду "вычислимо по Тьюрингу".
Развитие идеи МТ (а ведь кроме неё были и другие, например алгоритмы Маркова) позволило выяснить довольно интересные вещи. Например, умельцы смогли написать эмулятор машины Тьюринга на ней же, что позволило бы записывать программы прямо на ленте. В итоге концепция обросла кучей плюшек вроде адресуемой памяти и вылилась в первые образцы электронных машин.
![Goode
[ m ►
]
Поиск в Google
Мне повезёт!](http://img2.reactor.cc/pics/thumbnail/post-304951.jpg "Goode
[ m ►
]
Поиск в Google
Мне повезёт!")
Это реализация Машины Тьюринга. Зачем в таком виде - для прикола видимо.
Кроме всего прочего решаемость с помощью Машины Тьюринга является критерием решаемости задачи алгоритмически.
Логика взаимодействия со всем этим - в яблочко! В этим вся суть.
МТ есть прототип, послуживший основой для современной вычислительной техники. Работает с данными, записанными на ленте. Имеет набор заранее запрограммированных внутренних состояний.
Для каждой пары состояние + символ на ленте определяется действие - сдвиг ленты вправо/влево, запись символа или переход в другое состояние.
Многим теориям вычислительной математики удобно работать именно с машиной Тьюринга или её эквивалентом. Поэтому когда мы говорим "вычислимо" - мы имеем в виду "вычислимо по Тьюрингу".
Развитие идеи МТ (а ведь кроме неё были и другие, например алгоритмы Маркова) позволило выяснить довольно интересные вещи. Например, умельцы смогли написать эмулятор машины Тьюринга на ней же, что позволило бы записывать программы прямо на ленте. В итоге концепция обросла кучей плюшек вроде адресуемой памяти и вылилась в первые образцы электронных машин.