Презентация на тему: ""Алгоритмические машины в теории алгоритмов Машина Тьюринга Машина Поста""

Работу выполнила Ананина Ольга ученица 10 класса МБОУ «Цилемская СОШ»
Алгоритмические машины в теории алгоритмов
Машина Тьюринга
Машина Поста

Математическое понятие машина Тьюринга Английский математик Алан Тьюринг провел уточнение понятия алгоритма с помощью абстрактной математической машины. Основные свойства машины Тьюринга, отличающие её от исполнителя – человека, заключаются в следующим: машина Тьюринг не может ошибаться, т.е. она строго без всяких отклонений выполняет программу, определяющую ее работу; машина Тьюринг имеет потенциально бесконечную память.
Машина Тьюринга

1. Операция композиции
2. Операция ветвления
3. Операция зацикливаяния

Операции над машинами Тьюринга

Машина поста
В 1936 году американский математик и логик (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.
Машина Поста — это абстрактная (т. е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия. Тем не менее, на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы.

Машина поста
Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки.

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

Действия каретки подчинены программе, состоящей из перенумерованного набора команд (команды можно представлять как строки программы). Команды бывают шести типов:
1. записать 1 (метку), перейти к i-й строке программы;
2. записать 0 (стереть метку), перейти к i-й строке программы;
3. сдвиг влево, перейти к i-й строке программы;
4. сдвиг вправо, перейти к i-й строке программы;
5. останов;
6. если 0, то перейти к i, иначе перейти к j.
Машина поста

Команды машины Поста обозначаются следующим образом.

Машина поста

https://yandex.ru/images/search?from=tabbar&text=Машина%20Тьюринга%20н%20неформальном%20уровне&family=yes
https://yandex.ru/images/search?text=всякая%20мшина%20тьюринга%20представляет%20собой&from=tabbar&pos=2&img_url=https%3A%2F%2Fds05.infourok.ru%2Fuploads%2Fex%2F00a0%2F00023707-618638e7%2F31%2Fimg4.jpg&rpt=simage&lr=2&family=yes
https://infourok.ru/prezentaciya-po-informatiki-na-temu-algoritmicheskaya-mashina-tyuringa-klass-3290378.html
https://pandia.ru/text/81/298/72954.php