Явное му-рекурсивное выражение для функции Аккермана

Не могли бы вы указать, как построить функцию Аккермана (на самом деле меня интересует версия, предложенная Роузой Петером и Рафаэлем Робинсоном) с помощью стандартных мюрекурсивных операторов? Я пробовал оригинальные статьи Петера и Робинсона, но в работе Петера используется язык, отличный от английского, и работы Робинсона «Рекурсия и двойная рекурсия» и «Примитивные рекурсивные функции» также не помогают: первая из них кажется более актуальной, но использует ее так называется двойной операцией рекурсии для определения функции Аккермана, поэтому в этом случае ищется явное определение оператора в мюррекурсивных терминах.

Наиболее близко к ответу идет П. Смит в «Введение в теоремы Годеля» (CUP, 2007) (29.4 Функция Аккерманна-Петера µ-рекурсивна), но он приходит к следующему: «сделать аргумент водонепроницаемым довольно утомительно, хотя и не сложно. Изучать детали здесь нечего, поэтому мы не будем.

Я также попробовал книгу Рожи Петера «Рекурсивные функции» (1967, Academic Press). Существует множество вариантов операторов рекурсии. Обычно одно сводится к другому. Я считаю, что есть тип оператора рекурсии, который подходит для определения функции Аккермана и последовательности шагов, которые сводят ее к примитивным операторам перенаправления и минимизации, но я оказался не в состоянии исследовать весь путь вниз.

computability Артем Пеленицын
источник

На самом деле это не так сложно, как может показаться на первый взгляд. Хитрость заключается в том, чтобы позволить оператору

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

μ

$\mu$

Kaveh

и явное определение ограниченного умножения в терминах

рекурсии также можно найти в учебниках.

μ

$\mu$

Каве

@Kaveh да, та же идея реализована в «Введение в теоремы Годеля» П. Смита. Там приведены кодировки и применение оператора минимизации. Сложность в том, как создать «таблицу», как вы ее называете. Смит пропустил это. Так что, похоже, мне придется подумать над этим сложнее, чем ждать здесь решений;) По крайней мере, спасибо за ваше одобрение общего подхода.

Артем Пеленицын

Таблица - это просто конечная последовательность, где записи индексируются в результате функции сопряжения.

, где

μ c : \forall x < L e n (c) \forall y, z < x, x =< y, z >\to c_{< y, z >} = R (c, x, y)

$\mu c: \forall x<Len(c) \forall y,z<x , x=<y,z> \to c_{<y,z>} = R(c,x,y)$

R (c, x, y)

$R(c,x,y)$ является правой частью уравнения для

A c k (x, y)

$Ack(x,y)$

Каве

Ответы:

Разбить функцию Аккермана до элементарных операторов было бы довольно долго, но вот набросок:

Обратите внимание, что при вычислении рекурсивно, в любой точке вычисления вы имеете дело с выражением вида $A(m,x)$ . биективная функция сопряжения с обратным , мы можем закодировать это состояние как $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$ $p$ $(\pi_1,\pi_2)$ (просто в случае ). Затем мы можем определить одношаговую функцию оценки, учитывая состояние: $p(z,p(k,p(m_k,\dots,p(m_2,m_1)\dots)$ $p(z,0)$ $k=0$

; $e(p(z,0)) = p(z,0)$

; $e(p(z,p(k,p(0,c)))) = p(z+1,p(k-1,c))$

; $e(p(0,p(k,p(m+1,c)))) = p(1,p(k,p(m,c)))$

. $e(p(z+1,p(k,p(m+1,c)))) = p(z,p(k+1,p(m+1,p(m,c))))$

Затем вы получаете n-шаговую функцию оценки, используя примитивную рекурсию:

и $E(0,m,x) = p(x,p(1,m))$ . $E(n+1,m,x) = e(E(n,m,x))$

Наконец, оберните рекурсию вокруг $\mu$ $E$ чтобы найти точку, в которой мы до состояния вида - будет . $p(z,0)$ $z$ $A(m,x)$

Клаус Дрегер
источник

Благодарность! Еще один вопрос (может быть, довольно наивный, извините): определения, подобные сопоставлению с образцом (f (0) = ..., f (n + 1) = ...), широко используемые, но я сомневаюсь, что они действительно ослаблены определение му-рекурсивной функции. Они?

Артем Пеленицын

Такое различие в регистре (например, определение

через

f (x, y)

$f(x,y)$

f (0, y) = g (y)

$f(0,y)=g(y)$

) является лишь частным случаем примитивной рекурсии, которая на самом деле не использует предыдущее значение. При вычислении

, вы бы дополнительно использовали вспомогательные функции и обратные

f (x + 1, y) = h (x, y)

$f(x+1,y) = h(x,y)$

A (x, y)

$A(x,y)$

совсем немного, если вы хотите разбить это на основной набор операций.

π_{1}, π_{2}

$\pi_1,\pi_2$

Клаус Дрегер

Например, вы можете перевести определение

как

, где

e

$e$

e (s) = f_{1} (π_{1} (s), π_{2} (s))

$e(s)=f_1(\pi_1(s),\pi_2(s))$

f_{1} (z, 0) = p (z, 0)

$f_1(z,0)=p(z,0)$

, где

вы понимаете.

f_{1} (z, m + 1) = f_{2} (z, π_{1} (m + 1), π_{2} (m + 1))

$f_1(z,m+1)=f_2(z,\pi_1(m+1),\pi_2(m+1))$

f_{2} \dots

$f_2\dots$

Клаус Дрегер

Это вариант идеи, опубликованной Kaveh, но в любом случае я публикую ее, поскольку она позволяет вам подметать многие неприятные детали под ковер, фактически не делая никаких действий руками.

Ключевым фактом является то, что график функции Аккермана примитивно рекурсивен. Нетрудно найти очень грубую примитивную рекурсивную границу в коде для таблицы значений Аккермана, необходимых для проверки того, что . Не пытайтесь получить четкие границы - чем тяжелее, тем легче! Что-то вроде $B(m,n,w)$ $A(m,n) = w$ $B(m,n,w) = 2^{mw^w}$ должно быть достаточно хорошо, но это зависит от вашего выбора схемы кодирования. Поскольку проверка значений таблицы может быть описана ограниченной формулой, она является примитивно-рекурсивной.

Если у вас есть примитивно-рекурсивное определение для графа функции Аккермана, просто определите $G(m,n,w)$ . $A(m,n) = \mu w\,G(m,n,w)$

К сожалению, эта стратегия не работает для всех функций, определенных двойной (или множественной) рекурсией. Причина, по которой она работает для функции Аккермана - как вы увидите, пытаясь определить хороший - в том, что она растет очень монотонно. В общем случае вы должны использовать идею Каве и иметь $B(m,n,w)$ искать соответствующую таблицу значений. По сути, это та же самая причина, по которойтеореме Клини о нормальной форметребуется проекция после примененияоператора . $\mu$ $\mu$

Франсуа Г. Дорайс
источник

Привет Франсуа. Приятно видеть вас на истории.

Каве

Привет каве Приятно наконец получить что-то ответить здесь!

Франсуа Г. Дорайс