Гёделевская нумерация последовательностей - Gödel numbering for sequences

В математика, а Гёделевская нумерация последовательностей обеспечивает эффективный способ представления каждой конечной последовательности натуральных чисел как одного натурального числа. Хотя набор теоретических встраивание конечно возможно, акцент делается на эффективности функций, управляющих такими представлениями последовательностей: операции над последовательностями (доступ к отдельным членам, конкатенация) могут быть «реализованы» с использованием общие рекурсивные функции, а на самом деле примитивные рекурсивные функции.

Обычно он используется для построения последовательных «типы данных ”В формализации некоторых фундаментальных математических понятий, основанной на арифметике. Это частный случай более общей идеи Гёделевская нумерация. Например, теория рекурсивных функций можно рассматривать как формализацию понятия алгоритм, и может рассматриваться как язык программирования кривляться списки путем кодирования последовательности натуральных чисел в одно натуральное число.^[1][2]

Гёделевская нумерация

Основная статья: Гёделевская нумерация

Помимо использования нумерации Гёделя для кодирования уникальных последовательностей символов в уникальные натуральные числа (т.е. взаимоисключающий или же индивидуальная переписка с последовательностями), мы можем использовать его для кодирования целых «архитектур» сложных «машин». Например, мы можем закодировать Марковские алгоритмы,^[3] или же Машины Тьюринга^[4] в натуральные числа и тем самым доказать, что выразительная сила теории рекурсивных функций не меньше, чем у прежних машинных формализаций алгоритмов.

Доступ к участникам

Любое такое представление последовательностей должно содержать всю информацию, как в исходной последовательности - что наиболее важно, каждый отдельный член должен быть извлекаемым. Однако длина не обязательно должна совпадать напрямую; даже если мы хотим обрабатывать последовательности разной длины, мы можем хранить данные о длине как избыточный член,^[5] или как другой член упорядоченной пары, используя функция сопряжения.

Мы ожидаем, что существует эффективный способ для этого процесса поиска информации в форме соответствующей полной рекурсивной функции. Мы хотим найти полностью рекурсивную функцию ж с собственностью, которая для всех п и для любого п-длина последовательность натуральных чисел ${displaystyle langle a_{0},dots a_{n-1}angle }$, существует подходящее натуральное число а, называемый гёделевским числом последовательности, такой, что для всех я куда ${displaystyle 0leq ileq n-1}$, ${displaystyle f(a,i)=a_{i}}$.

Существуют эффективные функции, которые могут извлекать каждый член исходной последовательности из числа Гёделя последовательности. Более того, мы можем определить некоторые из них в конструктивный путь, так что мы можем выйти за рамки простого доказательства существования.

Лемма Гёделя о β-функциях

Смотрите также: Β-функция Гёделя

Остроумным использованием Китайская теорема об остатках, мы можем конструктивно определить такую ​​рекурсивную функцию ${displaystyle eta }$ (с использованием простых теоретико-числовых функций, все из которых могут быть определены полностью рекурсивным способом), выполняя технические характеристики приведено выше. Гёдель определил ${displaystyle eta }$ функция, используя китайскую теорему об остатках в его статье, написанной в 1931 году. примитивная рекурсивная функция.^[6]

Таким образом, для всех п и для любого п-длина последовательность натуральных чисел ${displaystyle langle a_{0},dots a_{n-1}angle }$, существует подходящее натуральное число а, называется гёделевским числом последовательности, такое что ${displaystyle eta (a,i)=a_{i}}$.^[7]

Использование функции сопряжения

Основная статья: Функция сопряжения

Наше конкретное решение будет зависеть от функции сопряжения - существует несколько способов реализации функции сопряжения, поэтому необходимо выбрать один метод. Теперь мы можем Абстрактные из деталей выполнение функции сопряжения. Нам нужно только знать его «интерфейс ": позволять ${displaystyle pi }$, K, и L обозначим функцию спаривания и ее два проекция функции, соответственно, удовлетворяющие Технические характеристики

${displaystyle Kleft(pi left(x,yight)ight)=x}$

${displaystyle Lleft(pi left(x,yight)ight)=y}$

Мы не будем здесь обсуждать и формализовать аксиому исключения инопланетных объектов, поскольку это не требуется для понимания метода.

Остаток для натуральных чисел

Мы будем использовать другую вспомогательную функцию, которая будет вычислять остаток от натуральных чисел. Примеры:

• ${displaystyle mathrm {rem} (5,3)=2}$
• ${displaystyle mathrm {rem} (7,2)=1}$

Можно доказать, что эта функция может быть реализована как рекурсивная функция.

Используя китайскую теорему об остатках

Реализация функции β

С использованием Китайская теорема об остатках, мы можем доказать, что реализация ${displaystyle eta }$ в качестве

${displaystyle eta (s,i)=mathrm {rem} left(Kleft(sight),left(i+1ight)cdot Lleft(sight)+1ight)}$

будет работать, согласно спецификации мы ожидаем ${displaystyle eta }$ удовлетворить. Мы можем использовать более сжатую форму, злоупотребление обозначениями (составляя своего рода сопоставление с образцом ):

${displaystyle eta left(pi left(x_{0},might),iight)=mathrm {rem} left(x_{0},left(i+1ight)cdot m+1ight)}$

Позвольте нам добиться еще большей читабельности за счет большего модульность и повторное использование (поскольку эти понятия используются в информатике^[8]): определяя ${displaystyle forall i<n}$ последовательность ${displaystyle m_{i}=(i+1)cdot m+1}$, мы можем написать

${displaystyle eta left(pi left(x_{0},might),iight)=mathrm {rem} left(x_{0},m_{i}ight)}$.

Мы будем использовать это ${displaystyle m_{i}}$ обозначения в доказательстве.

Настроенные вручную предположения

Для доказательства правильности приведенного выше определения ${displaystyle eta }$ функции мы будем использовать несколько лемм. У них есть свои предположения. Теперь мы пытаемся выяснить эти предположения, тщательно калибруя и настраивая их силу: о них нельзя говорить ни в излишне резкой, ни в неудовлетворительно слабой форме.

Позволять ${displaystyle a_{0},dots a_{n-1}}$ - последовательность натуральных чисел. м быть выбранным, чтобы удовлетворить

${displaystyle forall iin {overline {n}}setminus left{0ight}left(imid might)}$

${displaystyle forall i<nleft(a_{i}<m_{i}ight)}$

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

${displaystyle 1mid mland dots land n-1mid m}$

Это необходимо для выполнения предположения китайской теоремы об остатках (предположение о попарном совмещать ). В литературе иногда это требование заменяется более жестким, например конструктивно построен с факториал функция^[1] но для этого доказательства не требуется более сильной посылки.^[2]

Второе предположение никак не связано с китайской теоремой об остатках. Это будет иметь значение для доказательства того, что спецификация для ${displaystyle eta }$ в конце концов встречается. Это гарантирует, что ${displaystyle { ilde {x}}}$ решение системы одновременных сравнений

${displaystyle xequiv a_{i}{pmod {m_{i}}}}$ для каждого я куда ${displaystyle 0leq ileq n-1}$

также удовлетворяет

${displaystyle a_{i}=mathrm {rem} ({ ilde {x}},m_{i})}$.^[5][9]

Более сильное предположение для м требующий ${displaystyle forall i<n;(a_{i}<m)}$ автоматически удовлетворяет второму предположению (если мы определим обозначения ${displaystyle m_{i}}$ как указано выше).

Доказательство того, что условие (копримальности) китайской теоремы об остатках выполнено

В разделе Настроенные вручную предположения, мы потребовали, чтобы

${displaystyle forall iin {overline {n}}setminus left{0ight}left(imid might)}$. Мы хотим доказать, что можем создать последовательность попарных совмещать числа таким образом, чтобы они соответствовали Реализация функции β.

В деталях:

${displaystyle forall i<n,j<n;left(ieq jightarrow mathrm {coprime} left(m_{i},m_{j}ight)ight)}$

вспоминая это ${displaystyle forall i<n}$ мы определили ${displaystyle m_{i}=(i+1)cdot m+1}$.

Доказательство от противоречия; предполагаем отрицание исходного утверждения:

${displaystyle exists i<n,j<n;left(ieq jland lnot mathrm {coprime} left(m_{i},m_{j}ight)ight)}$

Первые шаги

Мы знаем, что означает «взаимно простое» отношение (к счастью, его отрицание может быть сформулировано в сжатой форме); таким образом, подставим соответствующим образом:

${displaystyle exists i<n,j<n;left(ieq jland exists pin mathrm {Prime} ;left(pmid m_{i}land pmid m_{j}ight)ight)}$

Используя «больше» пренекс нормальная форма (но обратите внимание на возможность обозначения в квантификаторах, похожего на ограничение):

${displaystyle exists i<n,j<n,pin mathrm {Prime} ;left(ieq jland pmid m_{i}land pmid m_{j}ight)}$

В силу теоремы о делимость, ${displaystyle pmid m_{i}land pmid m_{j}}$ позволяет нам также сказать

${displaystyle pmid m_{i}-m_{j}}$.

Подставляя определения из ${displaystyle m_{k}}$-последовательности, получаем ${displaystyle m_{i}-m_{j}=(i-j)cdot m}$, таким образом (как равенство аксиомы постулируют идентичность как отношение конгруэнтности ^[10]) мы получили

${displaystyle pmid (i-j)cdot m}$.

С п это главный элемент (обратите внимание, что неприводимый элемент свойство используется), получаем

${displaystyle pmid i-jlor pmid m}$.

Прибегая к первому настроенному вручную предположению

Теперь мы должны прибегнуть к нашему предположению

${displaystyle forall iin {overline {n}}setminus left{0ight}left(imid might)}$.

Предположение было выбрано тщательно, чтобы сделать его максимально слабым, но достаточно сильным, чтобы мы могли использовать его сейчас.

Предполагаемое отрицание исходного утверждения содержит соответствующее экзистенциальное утверждение с использованием индексов ${displaystyle i<nland j<nland ieq j}$; это влечет за собой ${displaystyle i-jin {overline {n}}setminus left{0ight}}$, поэтому упомянутое предположение может быть применено, поэтому ${displaystyle i-jmid m}$ держит.

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

Мы можем доказать несколькими способами ^[11] известно в пропозициональное исчисление который

${displaystyle left(Aland left(Aightarrow Bight)ight)ightarrow B}$

держит.

С ${displaystyle i-jmid m}$, посредством транзитивность собственность делимость связь, ${displaystyle pmid i-jightarrow pmid m}$. Таким образом (поскольку аксиомы равенства постулируют тождество как отношение конгруэнтности ^[10])

${displaystyle pmid m}$

можно доказать.

Приходя к противоречию

Отрицание исходного заявления содержало

${displaystyle pmid m_{i}}$

и мы только что доказали

${displaystyle pmid m}$.

Таким образом,

${displaystyle pmid m_{i}-left(i+1ight)cdot m}$

должен также держаться. но после замены определение из ${displaystyle m_{i}}$,

${displaystyle m_{i}-left(i+1ight)cdot m=1}$

Таким образом, резюмируя приведенные выше три утверждения, транзитивность из равенство,

${displaystyle pmid 1}$

также следует держать.

Однако в отрицании первоначального утверждения п является экзистенциально количественно и ограничен простыми числами ${displaystyle exists pin mathrm {Prime} }$. Это устанавливает противоречие, к которому мы стремились.

Конец сокращения до абсурда

Придя к противоречию с его отрицанием, мы только что доказали исходное утверждение:

${displaystyle forall i<n,j<n;left(ieq jightarrow mathrm {coprime} left(m_{i},m_{j}ight)ight)}$

Система одновременных сравнений

Строим систему одновременных сравнений

${displaystyle xequiv a_{0}{pmod {m_{0}}}}$

${displaystyle vdots }$

${displaystyle xequiv a_{n-1}{pmod {m_{n-1}}}}$

Мы можем написать это более кратко:

${displaystyle forall i<n;left(xequiv a_{i}{pmod {m_{i}}}ight)}$

Ниже будет сказано много утверждений, начиная с "${displaystyle forall i<n;left(dots ight)}$". Чтобы добиться более эргономичного обращения, отныне все утверждения следует рассматривать как относящиеся к сфере действия ${displaystyle forall i<n;left(dots ight)}$ количественная оценка. Таким образом, ${displaystyle forall i<n(}$ начинается здесь.

Выберем решение ${displaystyle x_{0}}$ для системы одновременных сравнений. Хотя бы одно решение должно существовать, потому что ${displaystyle m_{0},dots m_{n-1}}$ являются попарно простыми, как было доказано в предыдущих разделах, поэтому мы можем обратиться к решению, обеспечиваемому китайской теоремой об остатках. Таким образом, с этого момента мы можем рассматривать ${displaystyle x_{0}}$ как удовлетворение

${displaystyle x_{0}equiv a_{i}{pmod {m_{i}}}}$,

что означает (по определению модульная арифметика ) который

${displaystyle mathrm {rem} left(x_{0},m_{i}ight)=mathrm {rem} left(a_{i},m_{i}ight)}$

Прибегая к предположению, настроенному из вторых рук

Вспомните второе предположение: «${displaystyle forall i<n;left(a_{i}<m_{i}ight)}$», И помните, что сейчас мы находимся в рамках неявной количественной оценки я, поэтому мы не повторяем его количественную оценку для каждого утверждения.

Второе предположение ${displaystyle a_{i}<m_{i}}$ подразумевает, что

${displaystyle mathrm {rem} left(a_{i},m_{i}ight)=a_{i}}$.

Теперь по транзитивность из равенство мы получили

${displaystyle mathrm {rem} left(x_{0},m_{i}ight)=a_{i}}$.

QED

Нашей первоначальной целью было доказать, что определение

${displaystyle eta left(pi left(x_{0},might),iight)=mathrm {rem} left(x_{0},m_{i}ight)}$

подходит для достижения того, что мы заявили в спецификации ${displaystyle eta }$: мы хотим ${displaystyle eta left(pi left(x_{0},might),iight)=a_{i}}$ держать.

Теперь это можно увидеть по транзитивность из равенство, глядя на три приведенных выше уравнения.

(Большой объем я заканчивается здесь.)

Существование и уникальность

Мы только что доказали правильность определения ${displaystyle eta }$: его спецификация, требующая

${displaystyle forall a_{0},dots ,a_{n-1};exists s;forall i<n;eta (s,i)=a_{i}}$

встречается. Хотя доказательство этого было наиболее важным для создания схемы кодирования последовательностей, мы еще должны заполнить некоторые пробелы. Это связанные понятия, похожие на существование и уникальность (хотя в отношении уникальности здесь следует иметь в виду «максимум один», а соединение обоих откладывается в конечном результате).

Уникальность кодировки, достигнутая минимизацией

Наш главный вопрос: какое число должно обозначать кодировку последовательности ${displaystyle leftlangle a_{0},dots ,a_{n-1}ightangle }$? Спецификация декларирует только экзистенциальную количественную оценку, но еще не функциональную связь. Мы хотим конструктивный и алгоритмическое соединение: (полная) рекурсивная функция, которая выполняет кодирование.

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

Этот пробел можно восполнить несложным способом: воспользуемся минимизация, а совокупность результирующей функции обеспечивается всем, что мы доказали до сих пор (т. е. правильность определения ${displaystyle eta }$ соответствуя его спецификации). Фактически, спецификация

${displaystyle forall a_{0},dots ,a_{n-1};exists s;forall i<n;eta (s,i)=a_{i}}$

играет здесь роль более общего понятия («специальная функция»^[12]). Важность этого понятия состоит в том, что оно позволяет нам отделить (подкласс) (полных) рекурсивных функций от (суперкласса) частичных рекурсивных функций. Вкратце, в спецификации сказано, что функция ж^[13]удовлетворяет спецификации

${displaystyle fleft(a_{0},dots ,a_{n-1},sight)=0leftrightarrow forall i<n;left(eta (s,i)=a_{i}ight)}$

это специальная функция; то есть для каждой фиксированной комбинации всех, кроме последних аргументов, функция ж имеет корень в последнем аргументе:

${displaystyle forall a_{0},dots ,a_{n-1};exists s;left(fleft(a_{0},dots ,a_{n-1},sight)=0ight)}$

Гёделевскую нумерационную функцию g можно выбрать полностью рекурсивной.

Итак, выберем минимально возможное число, которое хорошо вписывается в спецификацию ${displaystyle eta }$ функция:^[5]

${displaystyle g:mathbb {N} ^{n} o mathbb {N} }$

${displaystyle leftlangle a_{0},dots ,a_{n-1}ightangle longmapsto mu a.left[forall i<n;left(eta left(a,iight)=a_{i}ight)ight]}$.

Можно доказать (используя понятия предыдущего раздела), что грамм является (полностью) рекурсивным.

Доступ длины

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

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

Чтобы проиллюстрировать оба случая: если мы формируем нумерацию Гёделя машины Тьюринга, то каждая строка в матрице «программы» может быть представлена ​​кортежами, последовательностями фиксированной длины (таким образом, без сохранения длины), потому что число столбцов фиксируется.^[14] Но если мы хотим рассуждать о вещах, подобных конфигурации (машин Тьюринга), и особенно если мы хотим закодировать значительную часть ленты работающей машины Тьюринга, то мы должны представить последовательности вместе с их длиной. Мы можем имитировать динамически растягивающиеся последовательности, представляя конкатенацию последовательностей (или, по крайней мере, дополняя последовательность еще одним элементом) полностью рекурсивной функцией.^[15]

Длина может храниться просто как добавочный элемент:^[5]

${displaystyle g:mathbb {N} ^{*} o mathbb {N} }$

${displaystyle leftlangle a_{0},dots ,a_{n-1},a_{n}ightangle longmapsto mu a.left[a_{0}=nland forall i<n;left(eta left(a,i+1ight)=a_{i}ight)ight]}$.

Соответствующая модификация доказательства проста, добавляя лишний

${displaystyle xequiv n{pmod {m_{0}}}}$

к системе одновременных сравнений (при условии, что индекс избыточного члена выбран равным 0). Кроме того, необходимо соответствующим образом изменить предположения.

Примечания

1. Монах 1976: 56–58
2. Чирмаз 1994: 99–100 (см. онлайн )
3. Монах 1976: 72–74
4. Монах 1976: 52–55
5. Чирмаз 1994: 100 (см. онлайн )
6. Смуллян 2003: 56 (= Глава IV, § 5, примечание 1)
7. Монах 1976: 58 (= Thm 3,46)
8. Хьюз 1989 (видеть онлайн В архиве 2006-12-08 в Wayback Machine )
9. Беррис 1998: Дополнительный текст, Арифметика I, Лемма 4
10. см. также связанные понятия, например «Равно за равных» (ссылочная прозрачность ) и другое родственное понятие закон Лейбница / идентичность неразличимых
11. либо теоретическое доказательство (алгебраические шаги); или семантический (таблица истинности, метод аналитических таблиц, Диаграмма Венна, Диаграмма Вейча / карта Карно )
12. Монах 1976: 45 (= По умолчанию 3.1.)
13. Например. определяется

    ${displaystyle f:mathbb {N} ^{n+1} o mathbb {N} }$

    ${displaystyle fleft(a_{0},dots ,a_{n-1},sight)={egin{cases}0&mathrm {if} ;forall i<n;left(eta (s,i)=a_{i}ight)1&mathrm {if} ;exists i<n;left(eta (s,i)eq a_{i}ight)end{cases}}}$

14. Монах 1976: 53 (= По умолчанию 3.20, лем 3.21)
15. Чирмаз 1994: 101 (= Thm 10.7, Conseq 10.8), см. онлайн

Рекомендации

• Беррис, Стэнли Н. (1998). «Дополнительный текст, арифметика I». Логика для математики и информатики. Прентис Холл. ISBN  978-0-13-285974-5.
• Чирмаз, Ласло; Хайнал, Андраш (1994). "Rekurzív függvények". Математикаи логика (постскриптум + gzip) | формат = требует | url = (помощь) (на венгерском). Будапешт: Университет Этвёша Лоранда. Каждую главу можно дословно загрузить на страница автора.
• Хьюз, Джон (1989). «Почему так важно функциональное программирование». Компьютерный журнал. 32 (2): 98–107. Дои:10.1093 / comjnl / 32.2.98. Архивировано из оригинал 8 декабря 2006 г.
• Монк, Дж. Дональд (1976). Математическая логика. Тексты для выпускников по математике. Нью-Йорк • Гейдельберг • Берлин: Springer-Verlag.
• Смуллян, Раймонд Меррилл (1992). Теоремы Гёделя о неполноте. Издательство Оксфордского университета. ISBN  978-0-19-504672-4.
• Смуллян, Раймонд Меррилл (2003). Gödel nemteljességi tételei (на венгерском). Будапешт: Typotex. ISBN  978-963-9326-99-6. Перевод Смуллян 1992.

внешняя ссылка

• Беррис, Стэнли Н. (1998). «Дополнительный текст, арифметика I». Логика для математики и информатики. Прентис Холл. ISBN  978-0-13-285974-5.