Нумерация Гёделя для последовательностей

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

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

Нумерация Геделя

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

Доступ к членам

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

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

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

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

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

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

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

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

${\displaystyle K\left(\pi \left(x,y\right)\right)=x}$

${\displaystyle L\left(\pi \left(x,y\right)\right)=y}$

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

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

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

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

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

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

Используя китайскую теорему об остатках , мы можем доказать, что реализация в виде ${\displaystyle \beta }$

${\displaystyle \beta (s,i)=\mathrm {rem} \left(K\left(s\right),\left(i+1\right)\cdot L\left(s\right)+1\right)}$

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

${\displaystyle \beta \left(\pi \left(x_{0},m\right),i\right)=\mathrm {rem} \left(x_{0},\left(i+1\right)\cdot m+1\right)}$

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

${\displaystyle \beta \left(\pi \left(x_{0},m\right),i\right)=\mathrm {rem} \left(x_{0},m_{i}\right)}$.

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

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

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

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

${\displaystyle \forall i\in {\overline {n}}\setminus \left\{0\right\}\left(i\mid m\right)}$

${\displaystyle \forall i<n\left(a_{i}<m_{i}\right)}$

Первое предположение подразумевает, что

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

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

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

${\displaystyle x\equiv a_{i}{\pmod {m_{i}}}}$для каждого i где ${\displaystyle 0\leq i\leq n-1}$

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

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

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

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

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

${\displaystyle \forall i\in {\overline {n}}\setminus \left\{0\right\}\left(i\mid m\right)}$. Мы хотим доказать, что мы можем создать последовательность попарно взаимно простых чисел таким образом, чтобы она соответствовала реализации функции β.

Подробно:

${\displaystyle \forall i<n,j<n\;\left(i\neq j\rightarrow \mathrm {coprime} \left(m_{i},m_{j}\right)\right)}$

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

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

${\displaystyle \exists i<n,j<n\;\left(i\neq j\land \lnot \mathrm {coprime} \left(m_{i},m_{j}\right)\right)}$

Первые шаги

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

${\displaystyle \exists i<n,j<n\;\left(i\neq j\land \exists p\in \mathrm {Prime} \;\left(p\mid m_{i}\land p\mid m_{j}\right)\right)}$

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

${\displaystyle \exists i<n,j<n,p\in \mathrm {Prime} \;\left(i\neq j\land p\mid m_{i}\land p\mid m_{j}\right)}$

Из-за теоремы о делимости , позволяет нам также сказать ${\displaystyle p\mid m_{i}\land p\mid m_{j}}$

${\displaystyle p\mid m_{i}-m_{j}}$.

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

${\displaystyle p\mid (i-j)\cdot m}$.

Поскольку p — простой элемент (обратите внимание, что используется свойство неприводимости элемента ), получаем

${\displaystyle p\mid i-j\lor p\mid m}$.

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

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

${\displaystyle \forall i\in {\overline {n}}\setminus \left\{0\right\}\left(i\mid m\right)}$.

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

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

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

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

${\displaystyle \left(A\land \left(A\rightarrow B\right)\right)\rightarrow B}$

держится.

Так как , по свойству транзитивности отношения делимости , . Таким образом (поскольку аксиомы равенства постулируют, что тождество является отношением конгруэнтности ^[10] ) ${\displaystyle i-j\mid m}$ ${\displaystyle p\mid i-j\rightarrow p\mid m}$

${\displaystyle p\mid m}$

может быть доказано.

Достижение противоречия

Отрицание исходного утверждения, содержащегося

${\displaystyle p\mid m_{i}}$

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

${\displaystyle p\mid m}$.

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

${\displaystyle p\mid m_{i}-\left(i+1\right)\cdot m}$

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

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

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

${\displaystyle p\mid 1}$

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

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

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

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

${\displaystyle \forall i<n,j<n\;\left(i\neq j\rightarrow \mathrm {coprime} \left(m_{i},m_{j}\right)\right)}$

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

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

${\displaystyle x\equiv a_{0}{\pmod {m_{0}}}}$

${\displaystyle \vdots }$

${\displaystyle x\equiv a_{n-1}{\pmod {m_{n-1}}}}$

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

${\displaystyle \forall i<n\;\left(x\equiv a_{i}{\pmod {m_{i}}}\right)}$

Ниже будет сказано много утверждений, все они начинаются с " ". Для достижения более эргономичного обращения, отныне все утверждения следует читать как находящиеся в сфере квантификации . Таким образом, начинается здесь. ${\displaystyle \forall i<n\;\left(\dots \right)}$ ${\displaystyle \forall i<n\;\left(\dots \right)}$ ${\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}\right)=\mathrm {rem} \left(a_{i},m_{i}\right)}$

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

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

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

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

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

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

ЧТЭК

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

${\displaystyle \beta \left(\pi \left(x_{0},m\right),i\right)=\mathrm {rem} \left(x_{0},m_{i}\right)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle f\left(a_{0},\dots ,a_{n-1},s\right)=0\leftrightarrow \forall i<n\;\left(\beta (s,i)=a_{i}\right)}$

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

${\displaystyle \forall a_{0},\dots ,a_{n-1}\;\exists s\;\left(f\left(a_{0},\dots ,a_{n-1},s\right)=0\right)}$

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

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

${\displaystyle g:\mathbb {N} ^{n}\to \mathbb {N} }$

${\displaystyle \left\langle a_{0},\dots ,a_{n-1}\right\rangle \longmapsto \mu a.\left[\forall i<n\;\left(\beta \left(a,i\right)=a_{i}\right)\right]}$.

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

Доступ длины

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

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

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

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

${\displaystyle g:\mathbb {N} ^{*}\to \mathbb {N} }$

${\displaystyle \left\langle a_{0},\dots ,a_{n-1},a_{n}\right\rangle \longmapsto \mu a.\left[a_{0}=n\land \forall i<n\;\left(\beta \left(a,i+1\right)=a_{i}\right)\right]}$.

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

${\displaystyle x\equiv n{\pmod {m_{0}}}}$

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

Примечания

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

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

    ${\displaystyle f\left(a_{0},\dots ,a_{n-1},s\right)={\begin{cases}0&\mathrm {if} \;\forall i<n\;\left(\beta (s,i)=a_{i}\right)\\1&\mathrm {if} \;\exists i<n\;\left(\beta (s,i)\neq a_{i}\right)\end{cases}}}$

14. Монк 1976: 53 (= Def 3.20, Lem 3.21)
15. Csirmaz 1994: 101 (=Thm 10.7, Conseq 10.8), см. онлайн

Ссылки

• Беррис, Стэнли Н. (1998). "Дополнительный текст, Арифметика I". Логика для математики и компьютерных наук . Prentice Hall. ISBN 978-0-13-285974-5.
• Чирмаз, Ласло; Хайнал, Андраш (1994). «Рекурсивные действия». Matematikai logika (постскриптум + gzip) (на венгерском языке). Будапешт: Университет Этвеша Лоранда.Каждую главу можно скачать дословно на странице автора.
• Хьюз, Джон (1989). «Почему функциональное программирование имеет значение». Computer Journal . 32 (2): 98–107. doi : 10.1093/comjnl/32.2.98 . Архивировано из оригинала 8 декабря 2006 г.
• Монк, Дж. Дональд (1976). Математическая логика . Тексты для аспирантов по математике. Нью-Йорк • Гейдельберг • Берлин: Springer-Verlag. ISBN 9780387901701.
• Смаллиан, Рэймонд Меррилл (1992). Теоремы Гёделя о неполноте . Oxford University Press. ISBN 978-0-19-504672-4.
• Смалльян, Рэймонд Меррилл (2003). Gödel nemteljessegi tételei (на венгерском языке). Будапешт: Тайпотекс. ISBN 978-963-9326-99-6.Перевод Смаллиана 1992 года.

Внешние ссылки

• Беррис, Стэнли Н. (1998). "Дополнительный текст, Арифметика I". Логика для математики и компьютерных наук . Prentice Hall. ISBN 978-0-13-285974-5.