Абстрактные автоматы. Машины Тьюдинга и Поста. (1017175)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

В 1936— 1937 гг. независимо друг от друга и почти одновременно с работами А. Черча и С. Клини было дано определение понятия алгоритма американским и английским математиками Э. Постом и А. Тьюрингом. Их подход базируется на определении специальных абстрактных (т. е. существующих не реально, а лишь в воображении) автоматов (машин). Основная мысль при этом заключалась в том, что алгоритмические процессы — это процессы, которые может со­вершать подходяще устроенная «машина». В соответствии с этим ими с помощью точных математических терминов были описаны классы машин, способные осуществить или имитировать все алгоритмиче­ские процессы, когда-либо описываемые математиками [2].

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

(рис. 5.2):

1) информационной ленты, представляющей собой бесконечную

(неограниченную) память машины. В качестве информационной ленты может служить магнитная или бумажная бесконечная лен­та, разделенная на отдельные ячейки. В каждой ячейке можно по­местить лишь один символ, в том числе и ноль;

2) «считывающей головки» — специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль голов­ки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты;

3) управляющего устройства, которое в каждый рассматрива­емый момент находится в некотором «состоянии». Предполагается, что устройство управления машины может находиться в некото­ром конечном числе состояний. Состояние устройства управления часто называют внутренним состоянием машины. Одно из этих со­стояний называется заключительным и управляет окончанием ра­боты машины.

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)