Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы (1107622), страница 8
Текст из файла (страница 8)
Затем переходит к соседней клетке всоответствии с запомненным тогда же сигналом протяжки.6. Если в ячейке, оказавшейся перед управляющей головкой, записан символ *, тоцепочка @@...@ m * (последний символ этой цепочки как раз и оказался передуправляющей головкой) переписывается на одну ячейку левее. Управляющая головкавозвращается к ячейке, перед которой она находилась перед переписью, и в эту ячейкузаписывается Λ (символ пустоты)247. Если состояние, в которое перешла моделируемая машина отлично от еезаключительного состояния, то переходим к этапу 2.8. Стоп.Существование универсальной машины Тьюринга непосредственно вытекает изгипотезы Тьюринга.
Однако, как видно из приведенной нами схемы работы, построениетакой машины может быть осуществлено непосредственно - без привлечения этойгипотезы. Такое построение можно рассматривать как дополнительное обоснованиеистинности гипотезы Тьюринга.ЛИТЕРАТУРА1. А.А.Марков, Н.М.Нагорный. Теория алгорифмов. - М., ФАЗИС, 1996.2. Б.А.Трахтенброт. Алгоритмы и вычислительные автоматы. - М., Сов. Радио, 1974.3.
Э.З.Любимский, В.В.Мартынюк, Н.П.Трифонов. Программирование. - М., Наука,1980.4. А.И.Мальцев. Алгоритмы и рекурсивные функции. - М., Наука, 1986.25СОДЕРЖАНИЕ1. О ЗАДАЧЕ ОБРАБОТКИ ИНФОРМАЦИИ...............................................................................................32. ПРОЦЕССЫ ОБРАБОТКИ ИНФОРМАЦИИ И АЛГОРИТМЫ..........................................................52.1. АЛГОРИТМ ЕВКЛИДА.............................................................................................................................52.2.
СВОЙСТВА АЛГОРИТМОВ.....................................................................................................................63. АЛГОРИТМЫ И ОТОБРАЖЕНИЯ.............................................................................................................74. ВЫЧИСЛИМЫЕ ФУНКЦИИ И ТЕЗИС ЧЕРЧА....................................................................................105. ФОРМАЛИЗАЦИЯ АЛГОРИТМА.............................................................................................................125.1.
МАШИНА ТЬЮРИНГА...........................................................................................................................135.1.1. ОБОСНОВАНИЕ ГИПОТЕЗЫ ТЬЮРИНГА....................................................................................175.2. НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА .........................................................................................186.
САМОПРИМЕНИМОСТЬ И ПРОБЛЕМА ПРИМЕНИМОСТИ........................................................227. УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА........................................................................................24ЛИТЕРАТУРА....................................................................................................................................................25СОДЕРЖАНИЕ ................................................................................................................................................2626.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
