Ghost_of_past про иерархию Хомского

[epros]

Я некоторое время назад проскочил мимо, а сейчас вспомнил. Тема, из которой это взято, в пургатории, но в ней это был явный офтоп, так что открываю новую тему и прошу прощения за некропостинг.

Ghost_of_past в сообщении #1644497 писал(а):

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

Хочу спросить: Откуда это всё взято? У меня есть сильное подозрение, что это либо недоразумение, либо взято из очень уж гуманитарных источников.

Вообще-то неограниченные языки по иерархии Хомского - это те, грамматика которых представляется любыми алгоритмами, включая не всегда имеющими точки останова. По этой причине грамматика при разборе предложений такого языка периодически бы "висла", что делает в общем случае применение неограниченных языков невозможным.

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

Большинство языков программирования, а также языки логики первого порядка, в которой формализуется большинство научного знания, являются по иерархии Хомского "контекстно свободными". На самом деле, этого вполне достаточно для выражения "чего угодно", ибо контекстно свободный язык может быть полным по Тьюрингу. Например, язык теории множеств первого порядка является полным по Тьюрингу, так что на нём можно формализовать самую витиеватую научную теорию. Правда цена простоты грамматики - большая сложность некоторых теорем, если мы захотим записать их на формальном языке.

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

[mihaild]

epros в сообщении #1647894 писал(а):

ибо контекстно свободный язык может быть полным по Тьюрингу

В каком смысле? Принадлежность слова контекстно-свободному языку легко проверяется за полиномиальное время.

epros в сообщении #1647894 писал(а):

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

Что тут "язык теории множеств" - множество формул (тогда неправда что он полон по Тьюрингу) или множество теорем (тогда неправда, что он контекстно свободен)?

(В каком смысле "естественный язык" сложный я не понимаю - можно без потери чего-либо полезного для практики ограничиться рассмотрением фраз длины не превосходящей $10^{100}$, а это вообще регулярный язык)

[Ghost_of_past]

epros в сообщении #1647894 писал(а):

Хочу спросить: Откуда это всё взято?

Про отнесение естественных человеческих языков к неограниченным?
Carl Pollard, Ivan A. Sag. 1994. Head-Driven Phrase Structure Grammar.
Noam Chomsky. 2000. New Horizons in the Study of Language and Mind.
Ivan A. Sag, Thomas Wasow, Emily M. Bender. 2003. Syntactic Theory: a formal introduction.

Впрочем, есть и более свежие концепции, например, идея выдвинутая рядом авторов (Gerhard Jäger, James Rogers), что естественные человеческие языки в полной мере степени вообще нельзя классифицировать по иерархии Хомского, так как один и тот же язык, в том числе и естественный, может в зависимости от ситуации использования переходить с одного уровня иерархии Хомского на другой - к примеру, они выдвигают гипотезу, что естественные языки могут считаться неограниченными лишь в идеальной ситуации применения, которая на практике де-факто невозможна, и по сути на практике естественные человеческие языки оказываются сильными контекстно-зависимыми языками. Но не будучи специалистом, я вынужден здесь придерживаться мейнстримного подхода Хомского и авторов HDPSG, как наиболее аргументированного.

Или про то, что у ряда других животных найдены потенциально сопоставимые по сложности системы коммуникации?
Claus Emmeche, Kalevi Kull. 2011. Towards a Semiotic Biology. Life is the Action of Signs.

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

epros в сообщении #1647894 писал(а):

либо взято из очень уж гуманитарных источников

Хомский как-то обходился без деления на гуманитарное и негуманитарное в этом исследовательском пространстве: посмотрите хотя бы его книгу "Cartesian Linguistics: A Chapter in the History of Rationalist Thought".

[epros]

mihaild в сообщении #1647897 писал(а):

epros в сообщении #1647894 писал(а):

ибо контекстно свободный язык может быть полным по Тьюрингу

В каком смысле? Принадлежность слова контекстно-свободному языку легко проверяется за полиномиальное время.

Полнота языка по Тьюрингу - это не про время проверки принадлежности предложения языку, а про возможность выразить на языке описание любой машины Тьюринга.

mihaild в сообщении #1647897 писал(а):

epros в сообщении #1647894 писал(а):

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

Что тут "язык теории множеств" - множество формул (тогда неправда что он полон по Тьюрингу) или множество теорем (тогда неправда, что он контекстно свободен)?

Язык теории множеств - это язык в синтаксисе исчисления предикатов первого порядка с единственным бинарным предикатным символом $\in$ в сигнатуре. С чего бы ему не быть полным по Тьюрингу? Прошу пояснить.

Множество теорем - это не про язык, а про теорию.

mihaild в сообщении #1647897 писал(а):

(В каком смысле "естественный язык" сложный я не понимаю - можно без потери чего-либо полезного для практики ограничиться рассмотрением фраз длины не превосходящей $10^{100}$, а это вообще регулярный язык)

Естественный язык "сложный" только в том смысле, что является контекстно зависимым (точнее, не является контекстно свободным) по иерархии Хомского. Это значит, что грамматическая интерпретация слов может зависеть от контекста.

[mihaild]

Так, для начала вопрос - что тут такое "язык". Или я совсем всё забыл, или одно из двух, поэтому на всякий случай базовые вещи.

Язык - это множество слов (конечных последовательностей символов). И иерархия Хомского именно про такие языки. Никакой "грамматической интерпретации" при этом не возникает.
Дальше вопрос - что такое Тьюринг-полнота для языка (а не для модели вычислений). Вроде бы стандартное определение (хотя не могу сейчас найти, так что может быть путаю): язык называется Тьюринг-полным, если к нему вычислимо сводится любой язык из RE. Понятно, что контекстно-свободный язык Тьюринг-полным быть не может.

И тут вопрос, что понимается под "языком теории множеств". Какое множество слов - формул исчисления предикатов в соответствующей сигнатуре? Тогда с чего бы ему быть Тьюринг-полным, как мне по коду МТ написать строчку в соответствующем алфавите, которая является корректной формулой если и только если эта МТ останавливается на пустом входе?

epros в сообщении #1647909 писал(а):

Множество теорем - это не про язык, а про теорию

Теоремы (некоторой теории) - это тоже множество слов. Для разумных теорий - перечислимое, но неразрешимое.

[epros]

mihaild, у нас явно какие-то непонятки с терминологией.

mihaild в сообщении #1647911 писал(а):

Так, для начала вопрос - что тут такое "язык". Или я совсем всё забыл, или одно из двух, поэтому на всякий случай базовые вещи.

Язык - это множество слов (конечных последовательностей символов).

Верно. Только то, что в формальной грамматике иногда называется "словами", в логике называется "предложениями". Собственно, грамматика может различать и отдельные слова (например, термы, которые не могут быть законченными предложениями), но её окончательная задача - построить (если грамматика порождающая) или распознать (если грамматика аналитическая) законченное предложение.

Поэтому да, язык - это такое подмножество строк, которые распознаются грамматикой как корректные предложения.

mihaild в сообщении #1647911 писал(а):

И иерархия Хомского именно про такие языки. Никакой "грамматической интерпретации" при этом не возникает.

"Грамматическая интерпретация" - это как раз про слова (которые не предложения) и даже может быть про отдельные символы. Когда я говорил про контекстную зависимость, я сказал, что слова могут интерпретироваться грамматикой по-разному в зависимости от контекста.

mihaild в сообщении #1647911 писал(а):

Дальше вопрос - что такое Тьюринг-полнота для языка (а не для модели вычислений). Вроде бы стандартное определение (хотя не могу сейчас найти, так что может быть путаю): язык называется Тьюринг-полным, если к нему вычислимо сводится любой язык из RE. Понятно, что контекстно-свободный язык Тьюринг-полным быть не может.

Что значит "к нему вычислимо сводится любой язык из RE"?

mihaild в сообщении #1647911 писал(а):

И тут вопрос, что понимается под "языком теории множеств". Какое множество слов - формул исчисления предикатов в соответствующей сигнатуре?

То подмножество строк, которые распознаются как корректные формулы теории множеств.

mihaild в сообщении #1647911 писал(а):

Тогда с чего бы ему быть Тьюринг-полным, как мне по коду МТ написать строчку в соответствующем алфавите, которая является корректной формулой если и только если эта МТ останавливается на пустом входе?

Причём тут останавливается или нет? Речь о том, что предложением языка можно определить любую машину Тьюринга, тогда язык является полным по Тьюрингу. Останавливается ли эта МТ, это другой вопрос.

Язык арифметики Пресбургера - не полон по Тьюрингу, только по этой причине в этом языке оказалось возможным определить полную (и даже алгоритмически разрешимую) теорию. А язык арифметики Робинсона (тем более - Пеано) уже полон по Тьюрингу. Только это позволяет в нём выполнить арифметизацию любой теории, следствием чего является Гёделевская неполнота теорий в данном языке (и в его расширениях).

mihaild в сообщении #1647911 писал(а):

epros в сообщении #1647909 писал(а):

Множество теорем - это не про язык, а про теорию

Теоремы (некоторой теории) - это тоже множество слов. Для разумных теорий - перечислимое, но неразрешимое.

Теоремы - это элементы множества утверждаемых теорией предложений языка. Язык за это не отвечает, он отвечает только за то, что строка является предложением.

[mihaild]

epros в сообщении #1647959 писал(а):

которые распознаются грамматикой как корректные предложения

Это то же самое, что "Язык - множество слов, порождаемых грамматикой", просто в других терминах, или что-то другое?

epros в сообщении #1647959 писал(а):

"Грамматическая интерпретация" - это как раз про слова (которые не предложения) и даже может быть про отдельные символы

Вот берем хотя бы википедию про иерархию Хомского: https://en.wikipedia.org/wiki/Chomsky_hierarchy. В зависимости от того, какие правила преобразования разрешены, получаются разные уровни иерархии. Где тут "интерпретация"?

epros в сообщении #1647959 писал(а):

Что значит "к нему вычислимо сводится любой язык из RE"?

Для любого перечислимого языка $L$ существует тотальная вычислимая функция $f$ такая что $x \in L$ тогда и только тогда, когда $f(x)$ из нашего языка.

epros в сообщении #1647959 писал(а):

как корректные формулы теории множеств

На всякий случай, "корректные" - это well formed? Т.е. $\exists x (x \in x \wedge x \not \in x)$ это корректная формула?

epros в сообщении #1647959 писал(а):

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

Что такое "определить"? Если нужно просто сопоставить каждую МТ какому-то предложению языка (вычислимо в обе стороны), то у Вас любой язык, содержащий бесконечное разрешимое множество полон по Тьюрингу.

epros в сообщении #1647959 писал(а):

Язык за это не отвечает, он отвечает только за то, что строка является предложением

epros в сообщении #1647959 писал(а):

Язык арифметики Пресбургера - не полон по Тьюрингу

epros в сообщении #1647959 писал(а):

А язык арифметики Робинсона (тем более - Пеано) уже полон по Тьюрингу

ЯННП. Я легко напишу как неразрешимую теорию в сигнатуре $(+, =)$, так и разрешимую в сигнатуре $(+, \cdot, <, =)$.
(в смысле задам разрешимое множество аксиом в соответствующих сигнатурах, так что множество теорем окажется разрешимым или нет)

[Cuprum2020]

Ghost_of_past в сообщении #1647906 писал(а):

Carl Pollard, Ivan A. Sag. 1994. Head-Driven Phrase Structure Grammar.
Noam Chomsky. 2000. New Horizons in the Study of Language and Mind.
Ivan A. Sag, Thomas Wasow, Emily M. Bender. 2003. Syntactic Theory: a formal introduction.

Ghost_of_past в сообщении #1647906 писал(а):

идея выдвинутая рядом авторов (Gerhard Jäger, James Rogers)

Ghost_of_past в сообщении #1647906 писал(а):

"Cartesian Linguistics: A Chapter in the History of Rationalist Thought".

Ghost_of_past в сообщении #1647906 писал(а):

Claus Emmeche, Kalevi Kull. 2011. Towards a Semiotic Biology. Life is the Action of Signs.

Ghost_of_past в сообщении #1647906 писал(а):

в принципе могу дать еще отдельные статьи

Каким бы узким рассматриваемый вопрос не казался, неизбежно окажется что kry перечитал именно по этому вопросу целую кипу книг и статей

[Ende]

Cuprum2020
Предупреждение за оффтоп и очередной переход на личности.

[Mikhail_K]

(Оффтоп)

Cuprum2020 в сообщении #1647967 писал(а):

Каким бы узким рассматриваемый вопрос не казался, неизбежно окажется что kry перечитал именно по этому вопросу целую кипу книг и статей

Ende в сообщении #1647976 писал(а):

Предупреждение за оффтоп и очередной переход на личности.

Гм. Я бы такое высказывание однозначно воспринимал как комплимент. Даже вне зависимости от того, замышлялось ли оно так автором высказывания.

[epros]

mihaild в сообщении #1647964 писал(а):

"Язык - множество слов, порождаемых грамматикой", просто в других терминах, или что-то другое?

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

mihaild в сообщении #1647964 писал(а):

Вот берем хотя бы википедию про иерархию Хомского: https://en.wikipedia.org/wiki/Chomsky_hierarchy . В зависимости от того, какие правила преобразования разрешены, получаются разные уровни иерархии. Где тут "интерпретация"?

В том, что не всякое правило контекстно зависимой грамматики разрешено в контекстно свободной. Те, что не разрешены, и порождают предложения, в которых возможность появления слова (внутри предложения) зависит от контекста. Правило контекстно зависимой грамматики $\alpha A \beta \to \alpha \gamma \beta$ порождает слово $\gamma$ в зависимости от контекста $\alpha$ и $\beta$.

mihaild в сообщении #1647964 писал(а):

Для любого перечислимого языка $L$ существует тотальная вычислимая функция $f$ такая что $x \in L$ тогда и только тогда, когда $f(x)$ из нашего языка.

Я не понял, это определение чего-то? Выглядит как ложное утверждение, ибо похоже, что не для всякого перечислимого языка такая функция существует.

mihaild в сообщении #1647964 писал(а):

На всякий случай, "корректные" - это well formed? Т.е. $\exists x (x \in x \wedge x \not \in x)$ это корректная формула?

Ну да, только $x \not \in x$ надо записать как $\neg x \in x$, ибо символа $\notin$ нет в сигнатуре.

mihaild в сообщении #1647964 писал(а):

Что такое "определить"? Если нужно просто сопоставить каждую МТ какому-то предложению языка (вычислимо в обе стороны), то у Вас любой язык, содержащий бесконечное разрешимое множество полон по Тьюрингу.

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

mihaild в сообщении #1647964 писал(а):

Я легко напишу как неразрешимую теорию в сигнатуре $(+, =)$, так и разрешимую в сигнатуре $(+, \cdot, <, =)$.
(в смысле задам разрешимое множество аксиом в соответствующих сигнатурах, так что множество теорем окажется разрешимым или нет)

Там ещё в сигнатуре должны быть $0$ и $1$. И бинарный предикатный символ $=$ можно использовать только как равенство, т.е. рефлексивность, симметричность и транзитивность должны быть. Неразрешимая в языке арифметики Пресбургера - это понятно. В конце концов, в теории без прикладных аксиом простейшие вещи типа $x+0=x$ будут неразрешимы. А разрешимую в языке арифметики Пеано: Я правильно понял идею, что можно просто определить "лишние" символы как синоним других, например, для $\cdot$ записать те же аксиомы, что и для $+$ в арифметике Пресбургера? Тогда получится теория, эквивалентная арифметике Пресбургера, а значит разрешимая.

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

[mihaild]

epros в сообщении #1647989 писал(а):

Я не понял, это определение чего-то?

Это определение Тьюринг-полного языка. Язык $L'$ Тьюринг-полон, если для любого перечислимого $L$ существует функция. Например язык из строк, кодирующих останавливающиеся машины Тьюринга, Тьюринг-полон.

epros в сообщении #1647989 писал(а):

Смоделировать любую частично рекурсивную функцию формулой языка

А что такое "формула языка"? То же самое, что и "предложение языка" (т.е. просто элемент языка)? Если да, то что такое "моделирование функций строками"?

epros в сообщении #1647989 писал(а):

в языке арифметики Пресбургера

Что такое "язык арифметики Пресбургера"? Корректная формула в соответствующей сигнатуре? Тогда как он связан с аксиомами?

epros в сообщении #1647989 писал(а):

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

Видимо да, аксиомы игнорируем. Тогда просто пишем аксиому $\forall x: x = 0$, и получаем исчисление высказываний.
И наоборот, для сигнатуры арифметики Пресбургера: берем аксиомы ZF, и заменяем в них $x\in y$ на $x + y = 0$.

Насколько я понимаю, выразимость вообще не про сигнатуру, а про конкретную ее модель. Там да, в модели $(\mathbb N, +)$ предикат $x|y$ невыразим.

[epros]

mihaild в сообщении #1647991 писал(а):

А что такое "формула языка"? То же самое, что и "предложение языка" (т.е. просто элемент языка)?

Да, в исчислении предикатов любая формула - предложение.

mihaild в сообщении #1647991 писал(а):

Если да, то что такое "моделирование функций строками"?

Например, пишем формулу $\varphi(y,x)$ и доказываем (из нами же придуманной аксиоматики), что при данном $x$ существует единственный $y$, ей удовлетворяющий, при этом он же является значением моделируемой функции при данном аргументе.

mihaild в сообщении #1647991 писал(а):

Что такое "язык арифметики Пресбургера"? Корректная формула в соответствующей сигнатуре? Тогда как он связан с аксиомами?

Язык-то никак не связан. Но вот что мешает на этом же языке выразить натуральные числа и их разложение на простые сомножители? Очевидно, всё же подразумевается, что знак $+$ должен выражать сложение, иначе Ваш трюк с заменой им знака $\in$ в теории множеств должен был бы сработать.

[mihaild]

(Мне видимо пора выписывать предупреждение за захват темы)

epros в сообщении #1647993 писал(а):

Например

А можете всё же написать более полное определение? Потому что пока что получается что у Вас понятие полноты по Тьюрингу применимо к очень специфическому классу языков (языкам формул в некоторой сигнатуре), а еще зависит не только от языка, но и от аксиоматики. Ну и понятно, что при не слишком бедной сигнатуре (вроде бы достаточно предикатного символа валентности хотя бы $2$, или предикатного символа валентности $1$ или равенства и функционального символа валентности хотя бы $2$) можно подобрать аксиоматику, при которой к языку из теорем будет сводиться язык из теорем ZF.

epros в сообщении #1647993 писал(а):

из нами же придуманной аксиоматики

Вот. Т.е. вопрос не только в языке, но и в аксиомах.
По сути у нас два языка - корректные формулы (зависящий только от сигнатуры), и теоремы (зависящие от аксиоматики). Корректные формулы - контекстно-свободный язык. Теоремы - как повезет, может быть даже неразрешимым (ну и понятно может быть неперечеслимым если аксиомы неперечислимы).

epros в сообщении #1647993 писал(а):

при этом он же является значением моделируемой функции

А для этого нам нужны не только аксиомы, но и модель.

epros в сообщении #1647993 писал(а):

Но вот что мешает на этом же языке выразить натуральные числа и их разложение на простые сомножители?

Неопределенность понятия "выразить разложение на простые сомножители в языке".

"В арифметике Пресбургера невыразима делимость" (что вообще такое "выразить разложение на простые сомножители"?) более строго означает "в сигнатуре $(+, =)$ при ее стандартной интерпретации в $\mathbb N$ невыразим предикат $x|y$ (определенный на $\mathbb N$)". Т.е. не существует формулы в этой сигнатуре с двумя свободными переменными, которая при этой интерпретации истинна ровно на нужных парах.

[epros]

mihaild в сообщении #1647994 писал(а):

Мне видимо пора выписывать предупреждение за захват темы

Мне кажется, что прояснение побочных вопросов, когда это приводит к реальному улучшению понимания используемых слов, не является криминалом. Иначе мы впадаем в грех философствования: Начинаем оперировать словами, значения которых не понимаем. Это я сейчас про употребление мной в стартовом посте словосочетания "полнота по Тьюрингу" применительно к языку. Собственно, я почерпнул это понятие из словарей и не планировал глубоко в него влезать. И Вы мне очень хорошо продемонстрировали, что это понятие содержит существенную семантическую составляющую, в словарях об этом не пишут. Спасибо Вам, избавили от греха.

На всякий случай поясню, что я хотел сказать в стартовом посте, упоминая "полноту языка по Тьюрингу". Я хотел сказать, что даже достаточно грамматически ограниченные языки (низких уровней иерархии по Хомскому) позволяют "выразить практически что угодно". Примером тому является синтаксис формальной теории множеств первого порядка. Просто я попытался слегка раскрыть непонятные слова про "выразимость чего угодно", указав на то, что любые алгоритмически формализуемые задачи, по крайней мере, могут быть описаны.

И это я говорил к тому, что в приписывании естественным языкам (включая, может быть, и языки животных) высокого места в иерархии Хомского - нет особой ценности. Наоборот, неограниченные языки, хотя формально и являются языками в том смысле, что каждый из них является множеством предложений, генерируемых алгоритмом, на практике вряд ли могут где-то применяться. Ибо грамматический анализатор на некоторых строках просто вис бы. А если мы заложим какой-то алгоритм прерывания повисшей аналитической грамматики, то скорее всего сделаем язык как минимум контекстно зависимым.

Поэтому я был сильно удивлён, что кто-то не относит естественные языки к контекстно зависимым. Возможно, авторы назвали их неограниченными в том смысле, что любой контекстно зависимый язык является неограниченным. Как-нибудь доберусь до указанных источников и почитаю.

mihaild в сообщении #1647994 писал(а):

epros в сообщении #1647993 писал(а):

из нами же придуманной аксиоматики

Вот. Т.е. вопрос не только в языке, но и в аксиомах.

Тут я специально подчеркнул, что аксиоматика придумана нами же, т.е. она по определению не относится к заданному нам языку.

mihaild в сообщении #1647994 писал(а):

По сути у нас два языка - корректные формулы (зависящий только от сигнатуры), и теоремы (зависящие от аксиоматики). Корректные формулы - контекстно-свободный язык. Теоремы - как повезет, может быть даже неразрешимым (ну и понятно может быть неперечеслимым если аксиомы неперечислимы).

Более или менее интересные теории неразрешимы, так что "язык теорем" получится заведомо даже не контекстно зависимым. Поэтому использовать его именно как язык я не вижу особого смысла, хотя формально под определение неограниченного языка он подходит. Собственно, весь смысл разделения грамматики и аксиоматики я вижу в том, что грамматика должна быть заведомо разрешима (и по возможности быстро), а аксиоматика скорее всего определит неразрешимую теорию.

mihaild в сообщении #1647994 писал(а):

epros в сообщении #1647993 писал(а):

при этом он же является значением моделируемой функции

А для этого нам нужны не только аксиомы, но и модель.

А что это такое? Модель в смысле теории моделей? Я имел в виду, что частично рекурсивная функция нам задана, например, в виде машины Тьюринга, и её "моделирование" заключается в том, что мы пишем формулу на заданном языке и определяем аксиоматику, позволяющую доказать эту формулу для тех значений аргумента, на которых частично рекурсивная функция определена.