Существует ли четкое определение «вычислимого» для моделей вычислений, которые не являются полностью точными?

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

Типичное определение вычислимости по Тьюрингу следующее:

Определение 1: Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга которая вычисляет с использованием подходящего кодирования натуральных чисел в виде строк.$f : \mathbb{N}^k \to \mathbb{N}$$M$$f$

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

Что теперь, если мы посмотрим на более слабые модели вычислений, чем машины Тьюринга? Например, давайте рассмотрим множество из «калек» машины Тьюринга с алфавитом , которая может двигаться только вправо, и определение калекой Тьюринга вычислимая которая согласуется с Тьюринга вычислимости:$M_c$$\{0,1\}$

Определение 2: функция называется калекой Тьюринга, вычислимой или вычислимой в M c$f : \mathbb{N}^k \to \mathbb{N}$$M_c$ если существует искалеченная машина Тьюринга которая вычисляет f с использованием подходящей кодировки натуральных чисел как строка$M$$f$

Если мы определим «подходящую кодировку» как «двоичного кодирования», то функция является не вычислимы в М с . Если мы аксиоматизируем «подходящее кодирование» как «унарное кодирование», то $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$$M_c$$f$ является вычислим в . Это кажется неловким, учитывая тот факт, что каждый может по своему усмотрению исправить одно из бесконечно многих интуитивных кодировок. Должно быть понятно, может ли вычислительная модель вычислить $M_c$$f$ или нет, не ссылаясь на какую-то конкретную кодировку - по крайней мере, я никогда не видел, чтобы кто-то упоминал, какая кодировка используется, когда говорится, что «программы цикла слабее машин Тьюринга».

После этого вступления я, наконец, могу сформулировать свой вопрос: как определить «подходящие кодировки» и «вычислимость» для произвольных моделей вычислений, которые не совпадают с интуитивным понятием вычислимости? Возможно ли это в рамках вычислимости вычислений?

Изменить: я сократил введение, это не добавило к вопросу.

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

По сути, вычислимость является свойством строковых функций . Когда вы определяете вычислимость в любом другом домене, вы должны исправить кодировку. На практике все «разумные» кодировки эквивалентны в смысле предыдущего абзаца, поэтому точное кодирование не имеет значения.$f\colon \Sigma^* \to \Sigma^*$

Однако кодирование имеет значение в ограниченных моделях вычислений. В качестве крайнего примера предположим, что вы рассматриваете ограниченные по времени машины Тьюринга: скажем, вы хотите, чтобы ваша машина завершила работу за время для некоторого c , где n - длина ввода (в виде строки). Мы больше не можем переключаться между двоичным и унарным кодированием, потому что двоичное кодирование намного компактнее. Когда мы говорим о вычисляемой функции целых чисел за полиномиальное время , мы указываем, что целые числа закодированы в двоичном виде. Даже это несколько произвольный выбор, поскольку десятичное кодирование привело бы к тому же понятию вычислимости за полиномиальное время.$O(n^c)$$c$$n$

Итак, чтобы ответить на ваш вопрос - кодировка указана как часть определения ограниченной модели.

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

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

Вы можете формализовать «подходящее кодирование», если вы зафиксируете машины Тьюринга в качестве эталонной модели вычислений, а затем потребуете, чтобы кодирование и декодирование из и в двоичные строки выполнялось машиной Тьюринга, которая всегда останавливается. Например, машина Тьюринга могла бы преобразовать натуральное число в виде двоичной строки в лямбда-член, который выражает это число, имитировать сокращение лямбда-исчисления и преобразовать результат обратно в двоичную строку.

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