Автор: Киселева Елена Валентиновна
Машина Тьюринга
Машина Тьюринга — созданная Аланом Тьюрингом в 1936 году абстрактная вычислительная машина, представляющая собой мыслительный эксперимент для решения проблемы математической логики.
Была использована для моделирования Квантового компьютера.
Данная машина состоит из нескольких частей:
1. Бесконечной в обе стороны (лево и право) ленты, поделенной на ячейки.
2. Головки, предназначенной для записи и чтения.
Головка способна записывать символ внешнего алфавита, в том числе и пустой, заменяя предыдущий; передвигаться на одну ячейку вправо или влево; менять состояние, указанное в программе.
3. Программы, управляющей головкой.
Программа записывается в виде таблицы и включает в себя внешний алфавит (конечное множество, элементами которого являются буквы/символы, при этом один из символов должен обозначать пустоту), внутренний алфавит(конечное множество состояний головки) и таблицу переходов (описание поведения головки, в зависимости от считанного символа/буквы и состояния).
Машина Поста
Машина Поста является абстрактной вычислительной машиной. Она была предложена Эмилем Постом в 1936 году, независимо от Машины Тьюринга. Она отличается от последней большей простотой.
Машина Поста так же состоит из трёх компонентов:
1. Бесконечной в обе стороны ленты, поделенной на равные ячейки, притом ячейка может быть пустой (0 или пустота) или содержать метку (1 или другой символ).
2. Каретки, передвигающейся по ленте на одну ячейку в обе стороны. Также она способна стирать, записывать и проверять метку.
3. Программы.
Программа здесь, вместо таблицы, записывается из набора команд, имеющих один синтаксис:
iKj, где i — номер команды, K — действие каретки, j — номер следующей выполняемой команды.
Всего для машины Поста существует 6 типов команд:
1. Vj — поставить метку и перейти к выполнению команды j.
2. Xj — стереть метку и перейти к выполнению команды j.
3. <-j — сдвинуть каретку влево и перейти к выполнению команды j.
4. ->j — сдвинуть каретку вправо и перейти к выполнению команды j.
5. ? j1;j2 — если в ячейке нет метки, перейти к выполнению команды j1, в противном случае перейти к выполнению команды j2.
6. ! — конец программы.