Czy istnieje jasna definicja „obliczalnego” dla modeli obliczeniowych, które nie są kompletne?

Jest to kontynuacja kolejnego pytania tutaj i mam nadzieję, że nie jest to zbyt filozoficzne. Jak zauważył Raphael w komentarzu do mojego poprzedniego pytania, tak naprawdę nie rozumiem definicji „obliczalnego”, ale zgodnie z niektórymi artykułami, które czytam, definicja nie jest również bardzo jasna, jeśli chodzi o modele obliczeń słabsze niż Turing maszyny ze względu na kodowanie wejścia i wyjścia.

Typowa definicja obliczania Turinga jest następująca:

Definicja 1: Funkcja nazywa się obliczalna Turinga, jeśli istnieje maszyna Turinga która oblicza przy użyciu odpowiedniego kodowania liczb naturalnych jako ciągów.$f : \mathbb{N}^k \to \mathbb{N}$$M$$f$

Definicje różnią się, co dokładnie jest odpowiednie kodowanie jest, ale większość odnosi się do binarnego kodowania , kodowanie jednoargumentowego lub kodowania dziesiętnego jako jednego stałego i odpowiedniego kodowania. Możliwe jest również wykazanie, że ustalenie jednego kodowania jest wymagane do zdefiniowania obliczalności Turinga. Ale co sprawia, że ​​powiedzmy, binarne kodowanie liczb naturalnych jest wyjątkowe, abyśmy mogli go aksjomatyzować jako jedyne odpowiednie kodowanie? Prawdopodobnie dlatego, że pasuje do intuicyjnego pojęcia, co oznacza obliczalność przypadkowo .

A co jeśli spojrzymy na słabsze modele obliczeń niż maszyny Turinga? Rozważmy na przykład zestaw „okaleczonych” maszyn Turinga z alfabetem który może poruszać się tylko w prawo, oraz definicję kalekiego obliczania Turinga, która jest zgodna z definicją obliczalności Turinga:$M_c$$\{0,1\}$

Definicja 2: Funkcja nazywa się kalekim obliczeniowym przetwarzaniem Turinga lub obliczalnym w iff istnieje sparaliżowana maszyna Turinga która oblicza przy użyciu odpowiedniego kodowania liczb naturalnych jako sznurek.$f : \mathbb{N}^k \to \mathbb{N}$$M_c$$M$$f$

Jeśli zdefiniujemy „odpowiednie kodowanie” jako „kodowanie binarne”, wówczas funkcja nie jest obliczalna w . Jeśli aksjomatyzujemy „odpowiednie kodowanie” jako „kodowanie jednoargumentowe”, wówczas można obliczyć w . Wydaje się to niezręczne, biorąc pod uwagę fakt, że każdy może naprawić dowolne z nieskończenie wielu intuicyjnych kodowań do woli. Powinno być jasne, czy model obliczeniowy może obliczać czy nie bez odwoływania się do jakiegoś konkretnego kodowania - przynajmniej nigdy nie widziałem, aby ktokolwiek wspominał, jakie kodowanie jest stosowane, gdy stwierdza się, że „programy pętli są słabsze niż maszyny Turinga”.$f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$$M_c$$f$ $M_c$$f$

Po tym wstępie mogę w końcu sformułować moje pytanie: Jak zdefiniować „odpowiednie kodowanie” i „obliczalność” dla dowolnych modeli obliczeń, które nie pokrywają się z intuicyjnym pojęciem obliczalności? Czy jest to możliwe w ramach obliczalności Turinga?

Edycja: Skróciłem wprowadzenie, nie dodało się do pytania.

Jednym z podstawowych faktów, których tu brakuje, jest to, że wszystkie wymienione kodowania są równoważne z punktu widzenia obliczalności: istnieje funkcja obliczalna odwzorowująca binarne kodowanie liczby na jej jednoargumentowe odwrotnie. Dlatego w celu zdefiniowania obliczalności nie ma znaczenia, które z tych kodowań wybierzesz dla liczb. Po prostu napraw swoje ulubione kodowanie.

Podstawą obliczalności jest właściwość funkcji łańcuchowych . Gdy definiujesz obliczalność w dowolnej innej domenie, musisz naprawić kodowanie. W praktyce wszystkie „rozsądne” kodowania są równoważne w rozumieniu poprzedniego akapitu, więc dokładne kodowanie nie ma znaczenia.$f\colon \Sigma^* \to \Sigma^*$

Kodowanie ma jednak znaczenie w ograniczonych modelach obliczeniowych. Dla skrajnego przykładu załóżmy, że rozważasz ograniczone czasowo maszyny Turinga: powiedz, że chcesz, aby twoja maszyna zakończyła się w czasie dla jakiegoś , gdzie jest długością danych wejściowych (jako ciąg). Nie możemy już przełączać się między kodowaniem binarnym a kodowaniem jednoargumentowym, ponieważ kodowanie binarne jest znacznie bardziej kompaktowe. Kiedy mówimy o funkcji liczb całkowitych obliczanej w czasie wielomianowym , określamy, że liczby całkowite są kodowane w postaci binarnej. Nawet to jest dość arbitralny wybór, ponieważ kodowanie dziesiętne prowadziłoby do tego samego pojęcia wielomianowego obliczania czasu.$O(n^c)$$c$$n$

Aby odpowiedzieć na twoje pytanie - kodowanie jest określone jako część definicji modelu z ograniczeniami.

Przede wszystkim nie można naprawić „odpowiedniego kodowania” jako ciągów binarnych ani żadnego innego kodowania. Wynika to z utraty wielu modeli obliczeń, ponieważ różne modele obliczeń mogą mieć bardzo różne modele danych wejściowych i wyjściowych. Innymi słowy, nie mogą „wymawiać” łańcuchów.

Na przykład, terminy niepopisanego rachunku lambda są albo zmiennymi, albo zastosowaniem jednego terminu do drugiego, albo abstrakcją terminu lambda. Dane wejściowe i wyjściowe to terminy, dowolne ciągi znaków. Mimo to niepisany rachunek lambda jest zakończony metodą Turinga, ponieważ istnieje „odpowiednie kodowanie”, które koduje liczby naturalne jako terminy lambda pewnej postaci, a pod tym kodowaniem dla każdej funkcji obliczalnej istnieje termin lambda, który go oblicza.

Możesz sformalizować „odpowiednie kodowanie”, jeśli naprawisz maszyny Turinga jako referencyjny model obliczeń, a następnie wymagać, aby kodowanie i dekodowanie zi do ciągów binarnych było wykonywane przez maszynę Turinga, która zawsze zatrzymuje się. Na przykład maszyna Turinga byłaby w stanie przetłumaczyć liczbę naturalną jako ciąg binarny na wyrażenie Lambda, które wyraża tę liczbę, zasymulować zmniejszenie rachunku lambda i przełożyć wynik z powrotem na ciąg binarny.

W przypadku prostszych modeli obliczeń oczekiwałbym tego samego podejścia: weź referencyjny model obliczeń i napraw kodowanie liczb naturalnych, a następnie upewnij się, że kodowanie i dekodowanie odbywa się za pomocą instancji tego prostego modelu. Jak zauważyłeś, w przypadku okaleczonych maszyn Turinga stosowanie liczb jedno- i binarnie kodowanych nie dałoby równoważnego modelu obliczeń.