Машина Поста

• Номер работы:
  558906
• Раздел:
  Все работы   →   Курсовые проекты - сложные   →   Математика (ВСЕ направления)
• Год добавления:
  31.05.2019 г.
• Объем работы:
  33 стр.
• Содержание:
  ВВЕДЕНИЕ 3
  1. ОБЩАЯ ХАРАКТЕРИСТИКА И НАЗНАЧЕНИЕ МАШИНЫ ПОСТА 5
  1.2. Сущность и принцип действия Машины Поста 5
  1.2. Многомерность машины поста 9
  2. ОСОБЕННОСТИ РЕАЛИЗАЦИИ ЗАДАЧ 15
  2.1. «Внешний вид» машины Поста. 15
  2.2. Практика исчислений 21
  2.3. Пример построения 27
  ЗАКЛЮЧЕНИЕ 30
  ПРИЛОЖЕНИЯ 33
  
  
• Выдержка из работы:
  Некоторые тезисы из работы по теме Машина Поста
  ВВЕДЕНИЕ
  
  Одной из фундаментальных статей, результаты которой лежат в основе современной теории алгоритмов является статья Эмиля Поста (Emil Post), «Финитные комбинаторные процессы, формулировка 1», опубликованная в 1936 году в сентябрьском номере «Журнала символической логики»
  Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решение общей проблемы это такое решение, которое доставляет ответ для каждой конкретной проблемы.
  Например, решение уравнения 3*х+9=0 – это одна из конкретных проблем, а решение уравнения a*x+b=0 – это общая проблема, тем самым алгоритм (сам термин «алгоритм» не используется Постом) должен быть универсальным, т.е. должен быть соотнесен с общей проблемой.
  Основные понятия алгоритмического формализма Поста – это пространство символов (язык L) в котором задаётся конкретная проблема и получается ответ, и набор инструкций, т.е. операций в пространстве символов, задающих как сами операции, так и порядок выполнения инструкций.
  ..................
  1. ОБЩАЯ ХАРАКТЕРИСТИКА И НАЗНАЧЕНИЕ МАШИНЫ ПОСТА
  
  
  1.2. Сущность и принцип действия Машины Поста
  Благодаря логическому выбору машина Поста может «принимать решение» в зависимости от текущих обстоятельств (выбирать куда ей переходить в зависимости от того есть ли запись в ячейке или она пуста). Кроме того, этот оператор выбора сам по себе породил новую алгоритмическую возможность как цикличность, чего формальная логика не имела в принципе.
  Еще очень важный момент, без которого эйдетическую логику трудно понять. Дело в том, что первая и вторая операция машины Поста используют не явным образом оператор эквивалентности. Они задают значения на ленте эквивалентные значениям алгоритма. Особенность этих операторов, что они задают их «в режиме записи». А вот в пятой операции Выбора оператор эквивалентности используется «в режиме чтения» – команда сначала считывает показание (помечена или нет ячейка), а потом действует соответственно. Как мы видим, оператор эквивалентностине явным образом присутствует в трех операторах из шести.
  ..........