СодержаниеСодержание
Машина Поста 3 стр.
Машина Тьюринга и алгоритмически неразрешимые проблемы 7 стр.
Список литературы 20 стр.ВведениеМАШИНА ПОСТА
________________________________________
1. Основные понятия и операции
Прежде чем рассматривать и модифицировать машину Тьюринга, остановимся на машине Поста (МП) [2, 6]. Именно она более всего соответствует современным процессорам и языкам программирования. Уже только этим машина Поста привлекает к себе, так как, с одной стороны, демонстрирует эффективность и работоспособность идеи, которой уже более полусотни лет, с другой — ее рассмотрение и анализ дают понимание причин сложившегося застоя в развитии программных систем. Сегодня, например, весьма актуальной становится проблема распараллеливания процессов, которую с помощью машины Поста (да, кстати, и Тьюринга тоже) решить сложно или даже невозможно, особенно если манипулировать «чистыми» абстрактными машинами. Возможно, проблема параллелизма во времена их создания была не столь актуальной, как ныне, а потому при их «изобретении» и не учитывалась.
Рис. 1. Машина Поста
Одной из фундаментальных статей, результаты которой лежат в основе современной теории алгоритмов является статья Эмиля Поста (Emil Post), «Финитные комбинаторные процессы, формулировка 1», опубликованная в 1936 году в сентябрьском номере «Журнала символической логики»
Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решение общей проблемы это такое решение, которое доставляет ответ для каждой конкретной проблемы.
Например, решение уравнения 3*х+9=0 – это одна из конкретных проблем, а решение уравнения a*x+b=0 – это общая проблема, тем самым алгоритм (сам термин «алгоритм» не используется Постом) должен быть универсальным, т.е. должен быть соотнесен с общей проблемой.
Основные понятия алгоритмического формализма Поста – это пространство символов (язык L) в котором задаётся конкретная проблема и получается ответ, и набор инструкций, т.е. операций в пространстве символов, задающих как сами операции, так и порядок выполнения инструкций.
Постовское пространство символов – это бесконечная лента ячеек (ящиков):
_ V _ _ V V V _ V
Каждый ящикЛитератураЛитература
1. Любченко В.С. Новые песни о главном-II//Мир ПК. 1998. №7. с.112.
2. Успенский В.А. Машина Поста. 2-е изд., испр. М.: Наука, 1988. 96 с. (Популярные лекции по математике).
3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций: Пер. с англ. М.: Мир, 1983. 256 с.
4. Кузьминский М. Вышел Merced из тумана//Computerworld Россия.1997. №47. С.31.
5. Хамби Э. Программирование таблиц решений. М.: Мир, 1976. 86 с.
6. Глушков В.М. Введение в кибернетику. Киев: Изд-во АН Укр ССР. 1964. 324 с.
7. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. М.: Мир, 1984. 264 с.
8. Краснов С.А. Транспьютеры, транспьютерные вычислительные системы и Оккам//Вычислительные процессы и системы / Под ред. Г.И. Марчука. Вып. 7. М.: Наука., 1990. 352 с.
|
