70Машина Поста.

Машина Поста (МП) — абстрактная вычислительная машина.

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние. Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис: i K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

V j - поставить метку, перейти к j-й строке программы.

X j - стереть метку, перейти к j-й строке программы.

<- j - сдвинуться влево, перейти к j-й строке программы.

-> j - сдвинуться вправо, перейти к j-й строке программы.

После запуска возможны варианты:

работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

работа может закончиться командой Stop;

работа никогда не закончится.

71Рекурсивные функции. Примитивно-рекурсивные функции. Примитивно-рекурсивные операторы. Частично-рекурсивные функции. Тезис Черча.

Определению Р. ф. может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда Р. ф. определяются как такие функции, которые можно получить из исходных в результате конечного числа применений упомянутых выше операций.

Функция f является примитивно-рекурсивной, если её можно получить из S1,O^n, конечным числом операций суперпозиции примитивной рекурсии.

Операторы подстановки и примитивной рекурсии определяются следующим образом:

         Оператор суперпозиции. Пусть f — функция от m переменных, а g1,..,gm — упорядоченный набор функций от n переменных каждая. Тогда результатом суперпозиции функций g_k в функцию f  называется функция h от n  переменных, сопоставляющая любому упорядоченному набору x₁,...,x_n  натуральных чисел число  h(x₁,...,x_n)=f(g₁(x₁,...,x_n),...,g_m(x₁,...,x_n))

         Оператор примитивной рекурсии. Пусть f — функция от n переменных, а  g — функция от n + 2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n + 1 переменной вида

h(x₁,...,x_n,0)=f(x₁,...,x_n)

h(x₁,...,x_n,y+1)= g(x₁,...,x_n,y, h(x₁,...,x_n,y))

В данном определении переменную y можно понимать как счетчик итераций, f — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций n переменных, начинающуюся с f,    g — как оператор, принимающий на вход n переменных x₁,...,x_n  , номер шага итерации (y) ,  функцию  на данном шаге итерации, и возвращающий функцию h(x₁,...,x_n,y) на следующем шаге итерации.

Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента. суперпози́ция фу́нкций — это применение одной функции к результату другой. Тезис Черча:Для любой интуитивно вычислимой функции существует вычисляющая её значения машина Тьюринга.