Есть ли понятие вычислимости на множествах, отличных от натуральных чисел?

Есть ли понятие вычислимости на множествах, отличных от натуральных чисел? Ради аргумента, скажем , на множествах $S$ , что biject с $\mathbb{N}$ .

Соблазнительно сказать «да, это те функции вида $g \circ f \circ g^{-1}$ где $g$ - любая биекция $\mathbb{N} \to S$ а $f$ - любая вычислимая функция $\mathbb{N} \to \mathbb{N}$ ». Я осторожен с этим определением по двум причинам.

1. Это дает преимущество $\mathbb{N}$ над другими счетными множествами. Почему $\mathbb{N}$ особенный, когда дело доходит до определения вычислимости? Мне бы хотелось, чтобы определение вычислимости было «без координат» без ссылки на какое-либо привилегированное множество, точно так же, как мне могло бы понравиться определение «без координат» понятия линейной алгебры без ссылки на какой-либо привилегированный базис.

2. Это поднимает вопрос о выборе $g$ . Я подозреваю, что возможно найти противоречия путем особенно патологического выбора $S$ и $g$ . Например, если я выберу $S = \mathbb{N}$ и $g$ некоторую невычислимую биекцию, действительно ли это так, что $g \circ f \circ g^{-1}$ вычислима для всех вычислимых $f$ ?

   Заманчиво требовать в определении, что $g$ вычислимо, но, к сожалению, это напрашивается на вопрос.

Существует ли какой-либо общий способ описания вычислимости на счетных множествах, отличных от $\mathbb{N}$ ?

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

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

«Вычислимые» числа могут быть кратко описаны как действительные числа, чьи выражения в виде десятичного числа вычисляются конечными средствами.

Иногда стоит вернуться к источнику.

Существует несколько способов установить вычислимость на общих множествах, одним из наиболее общих из которых является теория реализуемости . Идея теории реализуемости восходит к статье Клини « О интерпретации интуиционистской теории чисел» 1945 года, но с тех пор была обобщена и превращена в мини-ветвь вычислимости с хорошим сочетанием теории категорий, см., Например, книгу Яапа ван Остена «Реализуемость: введение в ее категоричную сторону» (Исследования по логике и основам математики, том 152, Elsevier, 2008).

Позвольте мне очень кратко описать идею реализуемости и обсудить ваше требование «без координат» позже. Начните с модели вычислений, такой как машины Тьюринга, $\lambda$ калькуляция, язык программирования или любая другая частичная комбинаторная алгебра (вы можете даже взять некоторые топологические пространства как «модели вычислений», этот материал является общим ). Для конкретности рассмотрим машины Тьюринга. Мы код машины Тьюринга с помощью натуральных чисел, но обратите внимание , что я мог бы взять какую - то другую модель вычислений, поэтому следует не считать , что использование $\mathbb{N}$ в любом случае существенным здесь. (Другие возможности включают в себя: powerset натуральных чисел, бесконечные последовательности натуральных чисел, синтаксис нетипизированных$\lambda$ калькуляция, некоторые категории игр и т. д.)

Структура вычислимости на множестве $X$ задается отношением $\Vdash_X$ между $\mathbb{N}$ и $X$ , называемым отношением реализуемости , так что для каждого $x \in X$ существует $n \in \mathbb{N}$ такой что$n \Vdash_X x$ . Мы называем такие конструкциисборками. Это определение напрямую соответствует интуитивной идее о том, что некоторый фрагмент данных$n$ представляет илиреализуетэлемент$x \in X$, (Например, определенные последовательности битов представляют собой конечные списки пар строк символов.)

Указанные две сборки $(X, {\Vdash_X})$ и $(Y, {\Vdash_Y})$ , отображение $f : X \to Y$ является реализуется (или "вычислимой") , если существует машина Тьюринга $T$ , таким образом, что всякий раз, когда $n \Vdash_X x$ , то $T(n)$ заканчивается и$T(n) \Vdash_Y f(x)$, Опять же, это прямая транслитерация того, что неофициально означает «программировать» абстрактную функцию $f$ : соответствующая машина Тьюринга выполняет представление данных независимо от того, что $f$ делает с соответствующими элементами.

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

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

Позвольте мне прокомментировать требование «без координат»:

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

• Набор $X$ может быть оснащен множеством структур вычислимости $\Vdash_X$ , так же как множество векторов имеет много базисов. Однако, хотя все базисы эквивалентны, не все структуры вычислимости на $X$ вычислимо эквивалентны.

• Если мы будем работать конкретно со структурами вычислимости $(X, {\Vdash_X})$ , это немного похоже на работу с матрицами в линейной алгебре. Это может быть очень полезно, но не абстрактно.

• Чтобы работать «без координат», мы работаем над реализацией и используем силу теории категорий (да, это клише, но это работает).

• Мы можем даже работать «без мира»: развивать математику в интуиционистской логике, а затем интерпретировать результаты в целях реализации.

В двух статьях ниже развивается понятие вычислимости для произвольных множеств. Интересно, что даже понятие теории сложности может быть определено для этой модели вычислений.

Функции рекурсивного множества Кобэма и теории слабых множеств Арнольд Бекман, Сэм Бусс, Си-Дэвид Фридман, Мориц Мюллер, Нил Тапен.

Ограниченная подмножеством рекурсия и модель схемы для функций рекурсивного множества Кобэма Арнольд Бекман, Сэм Бусс, Си-Дэвид Фридман, Мориц Мюллер, Нил Тапен.

Существует понятие сложности и вычислений над реалами. Учебник, на который я бы направил вас: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Я знаю одну лабораторию, которая изучает это специально: https://complexity.kaist.ac.kr/

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

Кроме того , для определения вычислимости на другое множество , закрепляю его с определенной частичной функцией из битовых строк в S . На самом деле не имеет значения, является ли эта функция биекцией, инъекцией или функцией любого другого типа (для случая, когда мы действительно не хотим, чтобы она была инъекцией, рассмотрим группу, определенную ее представлением, где у нас нет уникальное представление для его элементов). Это даже не должно быть сюрпризом, если мы допустим, что одноэлементные множества могут быть неисчислимыми. Составляя эту функцию с любой вычислимой биекцией из битовых строк в битовые строки (концепция уже определена), мы получаем определение вычислимости для $S$$S$$S$это инвариантно относительно функции, которую мы изначально выбрали (если мы выбрали что-то разумное). То есть, CT тезис для нашего множества . Но если мы не выберем разумную функцию, мы получим другое определение вычислимости.$S$

Эта функция также служит для определения вычислимости других функций с доменом или диапазоном , равной . Путем изменения диапазона к S , сохраняя домен , как { 0 , 1 } * , мы также получить O ( 1 ) инвариантное определение Колмогорова сложности для S . И мы можем наконец сказать, что выбранная нами функция сама по себе вычислима.$S$$S$$\{0,1\}^*$$O(1)$$S$

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

$S$$S$$S$$\{0,1\}^*$

$r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

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

$F:\mathbb{N} \rightarrow \mathbb{N}$$\mathbb{N}$$F:\mathbb{N} \rightarrow \mathbb{N}$