Машина Тьюринга

1.

Презентация на тему
Машина
Тьюринга

2.

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

3.

Что было создано с помощью Машины Тьюринга

4.

5.

Пентагон

6.

7.

Ничего, ведь
Машина Тьюринга
нужна для
вычислительных
операций.

8.

Машина Тьюринга — это абстрактная
вычислительная машина, мысленный
эксперимент для решения проблемы
математической логики. Она состоит
из трёх элементов:
бесконечной ленты с
ячейками;
автомата или головки для
чтения и записи;
программы.
«Машина снабжена „лентой“
(аналог бумаги), проходящей
через неё и разделённой на
участки (называемые квадратами),
каждый из которых может
содержать символ».
А. ТЬЮРИНГ,

9.

Принцип работы
машины Тьюринга

10.

Машина работает следующим
образом: головка может
прочитать содержимое
конкретной ячейки, стереть,
перезаписать и/или
передвинуться на ячейку влево
или вправо и повторить
считывание/запись.
«В некоторых конфигурациях, в которых ячейка
пуста (то есть не содержит символа), машина
записывает новый символ в эту ячейку: в
других конфигурациях она стирает символ.
Машина может также поменять ячейку, но
только путём смещения его на одно место
вправо или влево».
-
Тьюринг.

11.

Действия головки определяются
программой. Она записывается в
виде таблицы, где есть внешний и
внутренний алфавиты и таблица
переходов между ними. Внешний
алфавит — это конечное
множество, элементы которого
называются буквами или
символами. Внутренний алфавит —
это конечное множество состояний
головки. Таблица переходов
описывает поведение головки.
Команда, которую должна
выполнить головка, определяется
пересечением внешнего и
внутреннего алфавитов в таблице.
На рисунке выше изображена лента, входная информация
(11В) расположена так, что в каждой клетке по одному
символу. До и после неё — нулевые ячейки. Исходное
состояние головки — q1. Это состояние запускает работу
машины. Головка может сдвинуться влево и вместо 0
записать цифру или букву. Также она может сдвинуться
вправо и перезаписать 1 другой цифрой или буквой. Или
передвинуться ещё на ячейку влево/вправо без перезаписи.
Головка может также остаться на месте и ничего не делать.
Выполнение операций прекращается после того, как
головка считывает пассивное состояние — q0.

12.

Роль в истории
Историческое значение машины Тьюринга
в том, что это первая математическая
модель универсальных вычислений.
Другими словами, всё, что можно
вычислить, описывается как машина
Тьюринга. Это не единственная модель
вычислений, но, пожалуй, самая известная
и популярная. И ещё это описание работы
компьютера, которое Тьюринг дал до
появления компьютеров.
«Его машины предлагали мост, связь
между абстрактными символами и
физическим миром».
- Эндрю Ходжес
Также новаторство Тьюринга было в том, что его
машина использовала двоичную систему во
времена, когда преобладала десятичная.
Привычные для нас двоичные числа для
большинства читателей в 1936 году были не
столь знакомы. Так, компьютер ENIAC (1943–
1945) использовал десятичную систему. А слово
«бит» (сокращение от binary digit, «двоичная
цифра») появилось в публикациях только в 1948
году.
«Если автоматическая машина
печатает два вида символов, первый
из которых (называемый цифрами)
состоит исключительно из 0 и 1
(остальные называются символами
второго вида), то машина будет
называться вычислительной».
- А. Тьюринг

13.

Важность работы Тьюринга была ещё и в том,
что он описал универсальный компьютер
«общего назначения». Это революционная
концепция. В то время компьютеры
разрабатывались специально для определённых
видов работ. Например, Вэнивар Буш со
студентами в 1920-е годы придумал аналоговый
компьютер, известный как дифференциальный
анализатор. Он решал обыкновенные
дифференциальные уравнения — и это было
всё, что он делал.
«Не нужно разрабатывать разные машины для выполнения
различных вычислительных процессов. Все они могут быть
выполнены с помощью одного цифрового компьютера,
соответствующим образом запрограммированного для
каждого случая».
-
А. Тьюринг