Презентация, доклад на тему Автоматическая обработка информации (10 класс)

есть две части:
1) неограниченная в обе стороны лента, разделенная на ячейки;
2) головка для считывания/записи, управляемая программой.

A = {a1, a2, …, am} и алфавит состояний 
Q = {q1, q2, …, qm}. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q.) Состояние q0 называется заключительным, или состоянием останова. Считается, что если машина попала в это состояние, то она заканчивает свою работу. Состояние называется начальным. Находясь в этом состоянии, машина начинает свою работу.

ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит “пустая” буква а0 — признак того, что ячейка пуста).
Автомат может двигаться вдоль ленты влево или вправо, читать содержимое ячеек и записывать в ячейки буквы своего алфавита. Ниже схематично нарисована машина Тьюринга, автомат которой обозревает первую ячейку с данными.

какую букву он видит, а также в зависимости от своего состояния , автомат может выполнять следующие действия:
записать новую букву в обозреваемую ячейку;
выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
перейти в новое состояние.

записана команда.
Клетка (qj, ai) определяется двумя параметрами — символом алфавита и состоянием машины. Команда представляет собой указание: какой символ записать в текущую ячейку, куда передвинуть головку чтения/записи, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).

в частном случае совпадать с прежним состоянием qj). Следующую команду нужно искать в k-й строке таблицы на пересечении со столбцом, соответствующим букве, которую автомат видит после сдвига. В процессе работы автомат перескакивает из одной клетки программы, записанной в виде таблицы, в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q0, т.е. остановиться. Будем говорить, что такие клетки содержат команду останова.

над входным словом МТ никогда не окажется в заключительном состоянии, то считается, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она окажется в заключительном состоянии.

на ленте. Входное слово состоит из цифр целого десятичного числа, записанных в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа.
Решение. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре.

соответствующей машиной Тьюринга. Тезис Тьюринга является основной нематематической гипотезой теории алгоритмов, понимаемых по Тьюрингу. Одновременно этот тезис приводит к формальному определению алгоритма.
Алгоритм (по Тьюрингу) — программа для машины Тьюринга, приводящая к решению поставленной задачи.

способен решить любую алгоритмически разрешимую задачу. Этот фундаментальный результат был получен в то время, когда универсальных вычислительных машин еще не существовало. Более того, сам факт математического построения воображаемого универсального исполнителя позволил высказать предположение о целесообразности построения универсальной вычислительной машины, которая бы могла решать любые задачи при условии соответствующей кодировки исходных данных и разработки соответствующей программы действий исполнителя.

предложил иную абстрактную машину, характеризующуюся еще большей простотой, чем машина Тьюринга. Это строгое математическое построение было также предложено в качестве уточнения понятия алгоритма.

знака: 0 и 1 (ставить метку в ячейку или стирать метку). Это ограничение не влияет на ее универсальность, так как любой алфавит может быть закодирован двумя знаками. Кроме ленты, в машине Поста имеется каретка (головка чтения/записи), которая:
умеет двигаться вперед, назад и стоять на месте;
умеет читать содержимое, стирать и записывать 0 или 1;
управляется программой.

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

Поста заключается в том, что: “Всякий алгоритм представим в форме машины Поста”. Отсюда следует другое формальное определение алгоритма.
Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи. Тезис Поста невозможно строго доказать, так же, как и тезис Тьюринга.

и машина Тьюринга эквивалентны по своим возможностям. Более того, для каждого неформализованного алгоритма A существует формализованный алгоритм B (например, машина Тьюринга). В этом состоит полнота формализации понятия вычислимой функции.