Maszyna Turinga z nieskończonym alfabetem

Czy maszyna Turinga, która może odczytywać i zapisywać symbole z nieskończonego alfabetu, ma większą moc niż zwykła TM (to jedyna różnica, maszyna wciąż ma skończoną liczbę stanów)?

Intuicja mówi mi, że nie, ponieważ potrzebujesz nieskończonej liczby stanów, aby odróżnić każdy symbol. Myślę więc, że niektóre symbole lub przejścia spowodowane przez symbole (lub niektóre podzbiory przejść) muszą być równoważne. Tak więc możesz symulować taką maszynę za pomocą zwykłej bazy TM i ograniczonego podzbioru takich symboli lub przejść.

Jak podejść do tego formalnego dowodu?

Nie, byłby silniejszy. Funkcja przejścia nie byłaby już skończona, a to daje dużo energii.

Za pomocą nieskończonego alfabetu możesz zakodować dowolny element wejściowy z zestawu nieskończonego w jednym symbolu (chociaż zestaw wejściowy nie może być „bardziej nieskończony” niż zestaw alfabetu, np. Alfabet prawdopodobnie byłby tylko w nieskończoność nieskończony, więc elementy niepoliczalne zestawy takie jak liczby rzeczywiste nie mogą być reprezentowane w jednym symbolu). Podobnie w przypadku danych wyjściowych.

Możesz więc utworzyć dwustanowy (jeden początkowy, jeden akceptujący) nieskończony alfabet-TM z pojedynczym przejściem, które przechodzi w stan akceptacji i zmienia symbol pod głowicą taśmy zgodnie z funkcją, którą próbujesz obliczyć. Ten przepis pozwala obliczyć dowolne mapowanie między zestawami, które można umieścić w korespondencji jeden na jeden z alfabetem.

Aby uniknąć tego, że zdegenerowana maszyna jest odpowiedzią na wszystko, musisz ograniczyć możliwości przejścia. Oczywistym byłoby wymaganie, aby sama funkcja przejścia była obliczalna (zwykłe funkcje przejścia TM są przecież trywialnie obliczalne, ponieważ są skończone). Ale wtedy będziesz próbował użyć funkcji obliczeniowych do zdefiniowania modelu funkcji obliczalnych.

Powyższa odpowiedź jest poprawna, ale można powiedzieć coś więcej o nieskończonych alfabetach i obliczeniach.

Maszynę Turinga opisano w WP jako $M = (Q, \Gamma,b,\Sigma,\delta, q_0, q_f)$w których wszystkie zbiory są skończone. Zatem funkcja przejścia

$$\delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \{L,R \}$$ jest koniecznie skończony.

W maszynie z nieskończonym alfabetem zastępowalibyśmy wprowadzony alfabet $\Sigma$ powiedzmy $\Sigma^{inf}$ i alfabet taśmy według $\Gamma^{inf}$ oraz funkcję przejścia przez $\delta^{inf}$ słuchając:

$$\delta^{inf}: Q / F \times \Gamma^{inf} \rightarrow Q \times\Gamma^{inf} \times \{L,R \}$$

Więc $\delta^{inf}$jest koniecznie nieskończoną funkcją. Jak zauważono, jeśli ta funkcja ma być niepoliczalna, powyższe nie jest ostatecznie reprezentowalne. Załóżmy, że będziemy dotrzymywać$\delta^{inf}$(częściowe) rekurencyjne, jeśli to możliwe. Pytanie brzmi, czy alfabet zawsze na to pozwala.

Podstawową kwestią jest to, że skończony alfabet jest prezentowany w całości (dzięki czemu możemy zdefiniować nasze funkcje rekurencyjnie), ale nieskończonego alfabetu nigdy nie można przedstawić w całości. Jaki mechanizm generuje alfabet?

Najprostszym sposobem na rozważenie tego jest wyobrażenie sobie, że istnieje skończony „rdzeń” alfabetu, powiedzmy $A=\{a,b\}$. Następnie wygeneruj język$L \subset A^*$. Załóżmy, że ciąg abaab $\in L$. Następnie zdefiniuj$\alpha = <abaab> \in \Gamma^{inf}$. Tak więc nieskończony alfabet składa się z zestawów ciągów znaków od$L$połączone w pojedynczy symbol jak$<abaab>$.

Najprostszym takim alfabetem jest w zasadzie <1 *> , zwykły język, w którym rozróżnia się dowolne dwa symbole, zliczając liczbę kresek pionowych w każdym symbolu. Będzie to możliwe do obliczenia za pomocą parsera stanów skończonych (jednak jako LBA, a nie jako skończone automaty). Turing opowiadał się za skończonym alfabetem, aby uniknąć pojawienia się operacji nieskończonej w operacji TM. Warto jednak zauważyć, że 26 liter alfabetu angielskiego nie jest zgodne z tym wzorem liczenia: litera z nie zawiera 26 pociągnięć, kropek ani niczego. Możliwe są zatem inne wzorce z najbardziej ogólnym wzorcem obliczeniowym opartym na języku (re) rekurencyjnie wyliczalnym$L$.

Problemem jest tutaj to konstruowanie $\delta^{inf}$ nie będzie możliwe, chyba że definicja $L$jest wyraźnie podane. Wynika to częściowo z faktu, że równoważność powtórzeń jest nierozstrzygalna, a częściowo dlatego, że w przeciwnym razie mamy tylko skończoną próbkę do pracy i nie możemy wnioskować$L$z tego. Jeśli mamy definicję$L$ (i stąd $\Gamma^{inf}$) a następnie, jeśli $f$ jest rekurencyjny w $\Gamma^{inf}$ następnie $f$ jest rekurencyjne w skończonym A i tak dalej $f$ jest absolutnie rekurencyjny i $\delta^{inf}$ może być rekurencyjny.

Wreszcie rozważamy tę sprawę $L$ nie dotyczy dwóch przykładów:

Przykład 1 .$<n>\in \Gamma^{inf}$ iff $\phi_{n}(n)$możliwe do rozróżnienia. W tym przypadku alfabet$\Gamma^{inf}$oczywiście nie będzie miał skończonego opisu - zamiast tego będzie „rosnąć” w miarę upływu czasu (i będzie się w pełni definiował tylko w pewnych granicach obliczeniowych). Ale jest to nieskończony alfabet, którego w żadnym wypadku nie można przedstawić jednocześnie. Więc jeśli$f$ jest rekurencyjny w $\Gamma^{inf}$, a następnie f jest włączone $\Delta_2^0$- zestaw do zatrzymania. Więc$\delta^{inf}$ nie może być rekurencyjne.

Przyklad2 . Bardziej geometryczny przykład dotyczy płytek podobnych do Penrose'a . Niech symbol$S\in\Gamma^{inf}$ gdyby $S$jest jednostką N nieokresowych płytek, które w sposób pewny mogą pokryć płaszczyznę. Ten alfabet jest nieskończony, ponieważ dla każdego N można zbudować jednostkę N-kafelków płytek Penrose. Jednak układanie płaszczyzny jest nierozstrzygalne, więc zestaw S będzie się powiększał, gdy odkryje się więcej takich płytek. Możliwe$f$ rekurencyjny w $\Gamma^{inf}$ ale nie absolutnie rekurencyjne może być f (S) = liczba płytek w S.