Абстрактные автоматы. Машины Тьюдинга и Поста. (Ответы на экзаменационные билеты по информатике)
Описание файла
Файл "Абстрактные автоматы. Машины Тьюдинга и Поста." внутри архива находится в следующих папках: Ответы на экзаменационные билеты по информатике, информатика_ответы на билеты. Документ из архива "Ответы на экзаменационные билеты по информатике", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "Абстрактные автоматы. Машины Тьюдинга и Поста."
Текст из документа "Абстрактные автоматы. Машины Тьюдинга и Поста."
В 1936— 1937 гг. независимо друг от друга и почти одновременно с работами А. Черча и С. Клини было дано определение понятия алгоритма американским и английским математиками Э. Постом и А. Тьюрингом. Их подход базируется на определении специальных абстрактных (т. е. существующих не реально, а лишь в воображении) автоматов (машин). Основная мысль при этом заключалась в том, что алгоритмические процессы — это процессы, которые может совершать подходяще устроенная «машина». В соответствии с этим ими с помощью точных математических терминов были описаны классы машин, способные осуществить или имитировать все алгоритмические процессы, когда-либо описываемые математиками [2].
Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем стали называться машинами Тьюринга. В общем случае такая машина состоит из следующих частей
(рис. 5.2):
1) информационной ленты, представляющей собой бесконечную
(неограниченную) память машины. В качестве информационной ленты может служить магнитная или бумажная бесконечная лента, разделенная на отдельные ячейки. В каждой ячейке можно поместить лишь один символ, в том числе и ноль;
2) «считывающей головки» — специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль головки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты;
3) управляющего устройства, которое в каждый рассматриваемый момент находится в некотором «состоянии». Предполагается, что устройство управления машины может находиться в некотором конечном числе состояний. Состояние устройства управления часто называют внутренним состоянием машины. Одно из этих состояний называется заключительным и управляет окончанием работы машины.
Машины Тьюринга представляют собой универсальных исполнителей, с использованием которых можно имитировать все алгоритмические процессы, описываемые математиками. Доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций.
Таким образом, вопрос о существовании или несуществовании алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или несуществовании машины Тьюринга, обладающей нужным свойством.
В универсальной машине Тьюринга, как и во всякой тьюринговой машине, информация изображается символами, расположенными одновременно на магнитной ленте. При этом универсальная машина Тьюринга может располагать лишь фиксированным конечным внешним алфавитом. Между тем она должна быть приспособлена к приему в качестве исходной информации всевозможных состояний устройства управления и конфигураций, в которых могут встречаться символы из разнообразных алфавитов со сколь угодно большим числом различных символов.