|
|
Машина Тьюринга Сегодня в программе
Машина Тьюринга Сегодня в программе
4
Кто такой этот ваш шайтан-машина?
1
2
3
5
Внутренний мир машины Тьюринга
Варианты исполнения
Прочие абстрактные исполнители
Яркое завершение презентации и концерт Аллы Пугачёвой(опционально)
1.1 Кто такой этот ваш шайтан-машина? - Маши́на Тью́ринга (МТ) — абстрактный исполнитель. С помощью этого фомализовали понятие «алгоритм». А вот, кстати, и он! ---> Сделал это чудо мысли английский математик - Алан Тьюринг
1.2 Кто такой этот ваш шайтан-машина? - Машина Тьюринга - простейшее устройство, которое реализует действия по алгоритму, учитывающему текущее состояние устройства и состояние текущей ячейки памяти (традиционно говорят о "ленте"). В случае так называемой детерминированной (то есть определенной) машины Тьюринга, каждой паре состояний устройства и текущей ячейки соответствует единственное элементарное действие (которое может включать перемещение по памяти и изменение состояния ячеек). Эта теория используется для изучения принципов построения формальных алгоритмов на простейшем абстрактном примере.
2.1 Внутренний мир машины Тьюринга 2.2 Внутренний мир машины Тьюринга - Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит).
2.3 Внутренний мир машины Тьюринга - Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
- Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
- Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
3.1 Варианты исполнения - Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.
3.1 Варианты исполнения Машина Тьюринга, работающая на полубесконечной ленте Двумерные машины Тьюринга - Нормальный алгоритм (марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.
4.2 Прочие абстрактные исполнители - Машина поста Отличается от машины Тьюринга большей простотой, притом обе машины алгоритмически «эквивалентны» и обе разработаны для формализации понятия алгоритма и решения задач об алгоритмической разрешимости, то есть, демонстрации алгоритмического решения задач в форме последовательности команд для машины Поста
4.3 Прочие абстрактные исполнители - Лямбда-исчисление В основе лямбда-исчисления лежит понятие, известное ныне каждому программисту, — анонимная функция. В нём нет встроенных констант, элементарных операторов, чисел, арифметических операций, условных выражений, циклов и т. п. — только функции,
только хардкор - На этом презентация заканчивается
Пугачёва не приехала. Спасибо за внимание! - Презентацию подготовили: Савельев Завьялов Семёнов Бутовский Бобрик
|
|
|
Скачать 0.93 Mb.