Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы, страница 8
Описание файла
PDF-файл из архива "Л.С. Корухова, М.Р. Шура-Бура - Введение в алгоритрмы", который расположен в категории "". Всё это находится в предмете "практика расчётов на пэвм" из 1 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 8 страницы из PDF
Затем переходит к соседней клетке всоответствии с запомненным тогда же сигналом протяжки.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.