Czy istnieje pojęcie obliczalności dla zbiorów innych niż liczby naturalne?

Czy istnieje pojęcie obliczalności dla zbiorów innych niż liczby naturalne? Przez wzgląd na argument, powiedzmy na zestawy $S$ że biject z $\mathbb{N}$ .

To chciałoby się „tak, że to te funkcje formie $g \circ f \circ g^{-1}$ , gdzie $g$ oznacza dowolny bijection $\mathbb{N} \to S$ i $f$ jest dowolną funkcją obliczalną $\mathbb{N} \to \mathbb{N}$ ”. Jestem ostrożny z powodu tej definicji z dwóch powodów.

1. Uprzywilejowuje $\mathbb{N}$ stosunku do innych zbiorów policzalnych. Dlaczego jest $\mathbb{N}$wyjątkowy, jeśli chodzi o definiowanie obliczalności? Chciałbym definicję obliczalności „bez współrzędnych” bez odniesienia do jakiegokolwiek uprzywilejowanego zestawu w ten sam sposób, co podoba mi się definicja „bez współrzędnych” koncepcji algebry liniowej bez odniesienia do jakiejkolwiek uprzywilejowanej podstawy.

2. Rodzi pytania dotyczące wyboru $g$ . Podejrzewam, że możliwe jest znalezienie sprzeczności przez szczególnie patologiczne wybory $S$ i $g$ . Na przykład, jeśli wybiorę $S = \mathbb{N}$ i $g$ jakiegoś niepoliczalnego bijectionu, czy tak naprawdę jest tak, że $g \circ f \circ g^{-1}$ jest obliczalne dla wszystkich obliczalnych $f$ ?

   To kuszące, aby wymagać w definicji, że $g$ jest obliczalna, ale niestety to żebranie na pytanie.

Czy istnieje jakiś ogólny sposób opisywania obliczalności zbiorów policzalnych innych niż $\mathbb{N}$ ?

To pytanie nie jest na poziomie badawczym, ale ponieważ otrzymuje odpowiedzi, chciałbym zaoferować odpowiedź, która może nieco wyjaśnić sytuację i dostarczyć referencje.

Istnieje cała dziedzina informatyki teoretycznej, która bada możliwości obliczeniowe w analizie, algebrze i topologii. Kluczowe znaczenie ma pojęcie obliczalności dla liczb rzeczywistych. W rzeczywistości oryginalny artykuł Turinga na temat maszyn Turinga zaczyna się od następującego zdania:

Liczby „obliczalne” można krótko opisać jako liczby rzeczywiste, których wyrażenia w postaci dziesiętnej można obliczać skończonymi środkami.

Czasami warto wrócić do źródła.

Istnieje kilka sposobów konfigurowania obliczalności zbiorów ogólnych, z których jednym z najbardziej ogólnych jest teoria wykonalności . Idea teorii wykonalności wraca do pracy Kleene'a o interpretacji intuicyjnej teorii liczb z 1945 r., Ale od tego czasu została uogólniona i rozwinięta w mini-gałąź obliczalności z dobrą mieszanką teorii kategorii, patrz na przykład książka Jaapa van Oostena „Realizacja: wprowadzenie do jej kategorycznej strony” (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Pozwól, że opiszę krótko ideę wykonalności, a później omówię twój wymóg „bez współrzędnych”. Zacznij od modelu obliczeniowego, takiego jak maszyny Turinga, $\lambda$ rachunek, język programowania lub dowolna inna częściowa algebra kombinatoryczna (możesz nawet przyjąć pewne przestrzenie topologiczne jako „modele obliczeń”, to wszystko jest ogólne ). Dla konkretności rozważmy maszyny Turinga. Mamy kod Maszyna Turinga za pomocą liczb naturalnych, ale uwaga, że mogę wziąć jakiś inny model obliczeń, więc należy nie zakładać, że stosowanie $\mathbb{N}$ jest w żaden sposób niezbędny tutaj. (Inne możliwości obejmują: zestaw liczb naturalnych, nieskończone sekwencje liczb naturalnych, składnię nietypowego$\lambda$ rachunek, niektóre kategorie gier itp.)

Strukturę obliczalności na zbiorze $X$ podaje relacja $\Vdash_X$ między $\mathbb{N}$ i $X$ , zwana relacją wykonalności , tak że dla każdego $x \in X$ jest $n \in \mathbb{N}$ tak że $n \Vdash_X x$ . Takie konstrukcje nazywamy zespołami . Ta definicja bezpośrednio odpowiada intuicyjnemu poglądowi, że jakaś część danych $n$ reprezentuje lub realizuje element $x \in X$. (Na przykład niektóre sekwencje bitów reprezentują skończone listy par ciągów znaków.)

Biorąc pod uwagę dwa zespoły $(X, {\Vdash_X})$ i $(Y, {\Vdash_Y})$ , mapa $f : X \to Y$ jest realizowane (lub "obliczeniowy"), jeśli nie jest to maszyna Turinga $T$ , tak, że gdy $n \Vdash_X x$ czym $T(n)$ kończy się, a $T(n) \Vdash_Y f(x)$. Ponownie, jest to bezpośrednia transliteracja tego, co to znaczy nieoficjalnie „zaprogramować” abstrakcyjną funkcję $f$ : odpowiednia maszyna Turinga reprezentuje dane niezależnie od tego, co $f$ robi z odpowiednimi elementami.

Zespoły można rozszerzyć do topów wykonalności . Topos jest modelem matematyki intuicyjnej wyższego rzędu. To mówi nam, że każdy topos wykonalności (jeden dla każdego modelu obliczeń) zawiera wiele interesujących obiektów. Na przykład zawiera obiekt liczb rzeczywistych, co daje nam możliwość obliczeń na liczbach rzeczywistych. Ale zawiera również wiele innych obiektów, takich jak przestrzenie Hilberta, przestrzenie Banacha, przestrzenie gładkich map itp. Poprosiłeś o inną strukturę obliczalną, ale uzyskałeś coś znacznie lepszego: całe matematyczne światy obliczeniowe.

Ponieważ teoria kategorii i topozy mogą być przerażające i wymagają pewnej biegłości technicznej w teorii obliczalności, teorii kategorii i logice, moglibyśmy również pracować tylko w jednym konkretnym toposie, ale wszystko wyrażamy w konkretne, nieabstrakcyjne sposoby. Szczególnie dobry świat obliczeń wynika z możliwości realizacji funkcji Kleene i jest nazywany analizą obliczeniową .

Pozwól mi skomentować wymóg „bez współrzędnych”:

• Przełączanie między modelami obliczeń daje różne rodzaje światów obliczeniowych. To trochę jak przełączanie między różnymi polami, dając różne rodzaje algebry liniowej.

• Zbiór $X$ może być wyposażony w wiele struktur obliczeniowych $\Vdash_X$ , podobnie jak zbiór wektorów ma wiele zasad. Jednak chociaż wszystkie zasady są równoważne, nie wszystkie struktury obliczeniowe na $X$ są obliczeniowo równoważne.

• Jeśli pracujemy konkretnie ze strukturami obliczalności $(X, {\Vdash_X})$ , to trochę przypomina pracę z macierzami w algebrze liniowej. Może być bardzo przydatny, ale nie jest abstrakcyjny.

• Aby pracować w sposób „bez współrzędnych”, pracujemy w toposach wykonalności i wykorzystujemy moc teorii kategorii (tak, to banał, ale działa).

• Możemy nawet pracować w sposób „wolny od świata”: rozwijać matematykę w logice intuicyjnej, a następnie interpretować wyniki w topach wykonalności.

W dwóch poniższych artykułach opracowano pojęcie obliczalności dla dowolnych zbiorów. Co ciekawe, nawet dla teorii modelu obliczeniowego można zdefiniować pojęcie teorii złożoności.

Funkcje zestawu rekurencyjnego Cobhama i teorie słabego zestawu Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Rekurencja z podzbiorem i model obwodu dla rekurencyjnych funkcji Cobhama Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Istnieje pojęcie złożoności i obliczeń rzeczywistych. Podręcznik, do którego skierowałbym cię, to: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Znam jedno laboratorium, które bada to konkretnie: https://complexity.kaist.ac.kr/

Jest to podobne do tego, jak definiujemy obliczalność w odniesieniu do maszyn Turinga, a następnie szybko zapominamy o maszynach Turinga. Ponieważ okazuje się, że maszyna Turinga jest równie dobrą definicją, jak każda inna, używamy jej jako kotwicy dla całej klasy równoważności modeli i otrzymujemy tę samą klasę bez względu na to, z którego elementu ją generujemy. Zasadniczo jest to teza Churcha-Turinga i określa zbiór obliczalnych ciągów bitów.

Podobnie, w celu określenia Obliczalność innego zestawu , to umieścić go w określonej funkcji parcjalnym ciągi bitów do S . W rzeczywistości nie ma znaczenia, czy ta funkcja jest wstrzyknięciem, zastrzykiem, czy jakimkolwiek innym rodzajem funkcji (w przypadku, gdy tak naprawdę nie chcemy, aby to był zastrzyk, rozważ grupę zdefiniowaną przez jego prezentację, w której nie mamy unikalna reprezentacja jego elementów). Nie musi to nawet być przesadą, jeśli pozwolimy, aby zestawy singletonów były niepoliczalne. Komponując tę ​​funkcję z dowolnym obliczalnym bijectem z ciągów bitów na ciągi bitów (koncepcja już zdefiniowana), otrzymujemy definicję obliczalności dla $S$$S$$S$jest to niezmienne w stosunku do funkcji, którą pierwotnie wybraliśmy (o ile wybraliśmy coś rozsądnego). Oznacza to, że teza CT dla naszego zestawu . Ale jeśli nie wybieramy rozsądnej funkcji, otrzymamy inną definicję obliczalności.$S$

Ta funkcja służy również do określenia Obliczalność innych funkcji w domenie lub zakresie równym . Zmieniając zakres na S , utrzymując domenę jako { 0 , 1 } * , możemy również uzyskać O ( 1 ) -invariant definicję Złożoność Kołmogorowa dla S . I możemy wreszcie powiedzieć, że wybraną przez nas funkcję można obliczyć.$S$$S$$\{0,1\}^*$$O(1)$$S$

Myślę więc, że odpowiedź na twoje pytanie brzmi NIE. Musimy zdefiniować obliczalność dla każdego zestawu, o którym chcemy rozmawiać, ponieważ istnieją definicje nie równoważne. Oprócz bardzo technicznej lub pedagogicznej dyskusji nie powinno to być konieczne, ponieważ rozsądna osoba może samodzielnie wyobrazić sobie rozsądną definicję.

Ale poczekaj, niech będzie niezliczonym zestawem nieskończonym i tyle. Jaka jest nasza rozsądna definicja obliczalności dla S ? Wiedząc, że zestaw bijectycji między S a { 0 , 1 } ∗ jest niepusty, nie mówi nam, które są rozsądne. Nie mamy szczęścia bez dalszych szczegółów.$S$$S$$S$$\{0,1\}^*$

I możemy napotkać wiele nierównych, ale jednakowo rozsądnych alternatyw. Załóżmy, że każde drzewo ma pewną liczbę czerwonych liści i pewną liczbę zielonych liści i że dla każdego istnieje dokładnie jedno drzewo z r czerwonymi liśćmi i że dla każdego g ∈ N istnieje dokładnie jedno drzewo o g zielonych liści. Oba bijections są rozsądne w tym sensie, że możemy policzyć liście i rozróżnić kolory, i możemy bez celu chodzić po lesie licząc liście na drzewach, aż znajdziemy drzewo z dokładnie 23 zielonymi liśćmi lub ten z $r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$czerwone liście. Nie jest jasne, czy zidentyfikować drzewo za pomocą jego liczby czerwonych liści, czy liczby zielonych liści, ponieważ ten wybór prowadzi do nierównych definicji obliczalności dla zestawów drzew. Jeśli zamiast tego zdefiniujemy naszą definicję, łącząc liczby z obliczalną funkcją parowania bijective z do N (mając odpowiednio zdefiniowaną obliczalność na N 2 ), to również jednoznacznie identyfikuje każde drzewo, ale sytuacja jest jeszcze gorsza, ponieważ nie jest to bijection między drzewami i N , może teraz wszystkie obliczalne zestawy drzew są skończone!$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

Aby więc uniknąć całej dyskusji, należy zrozumieć nie tylko, że istnieje rozsądna definicja obliczalności na danym zbiorze, ale także, że istnieje dokładnie jedna klasa rozsądnych definicji.

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