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?
Odpowiedzi:
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.
źródło
Powyższa odpowiedź jest poprawna, ale można powiedzieć coś więcej o nieskończonych alfabetach i obliczeniach.
Maszynę Turinga opisano w WP jakoM=(Q,Γ,b,Σ,δ,q0,qf) w których wszystkie zbiory są skończone. Zatem funkcja przejścia
W maszynie z nieskończonym alfabetem zastępowalibyśmy wprowadzony alfabetΣ powiedzmy Σinf i alfabet taśmy według Γinf oraz funkcję przejścia przez δinf słuchając:
Więcδ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ćδ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, powiedzmyA={a,b} . Następnie wygeneruj językL⊂A∗ . Załóżmy, że ciąg abaab ∈L . Następnie zdefiniujα=<abaab>∈Γinf . Tak więc nieskończony alfabet składa się z zestawów ciągów znaków odL 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 wyliczalnymL .
Problemem jest tutaj to konstruowanieδ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 Γinf ) a następnie, jeśli f jest rekurencyjny w Γinf następnie f jest rekurencyjne w skończonym A i tak dalej f jest absolutnie rekurencyjny i δinf może być rekurencyjny.
Wreszcie rozważamy tę sprawęL nie dotyczy dwóch przykładów:
Przykład 1 .<n>∈Γinf iff ϕn(n) możliwe do rozróżnienia. W tym przypadku alfabetΓ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ślif jest rekurencyjny w Γinf , a następnie f jest włączone Δ02 - zestaw do zatrzymania. Więcδinf nie może być rekurencyjne.
Przyklad2 . Bardziej geometryczny przykład dotyczy płytek podobnych do Penrose'a . Niech symbolS∈Γ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żliwef rekurencyjny w Γinf ale nie absolutnie rekurencyjne może być f (S) = liczba płytek w S.
źródło