Maszyna Turinga z nieskończonym alfabetem

9

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?

zad
źródło
7
Jednocześnie crossposted na CSTheory. Proszę nie rób tego. Sprawia, że ​​twoje pytanie wydaje się ważniejsze niż inne. Jest to prawdopodobnie bardziej odpowiednie tutaj.
Juho

Odpowiedzi:

17

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.

Ben
źródło
6

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,Γ,b,Σ,δ,q0,qf)w których wszystkie zbiory są skończone. Zatem funkcja przejścia

δ:Q/F×ΓQ×Γ×{L,R}
jest koniecznie skończony.

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:

δinf:Q/F×ΓinfQ×Γinf×{L,R}

Więc δinfjest 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, powiedzmy A={a,b}. Następnie wygeneruj językLA. 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 odLpołą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 Ljest 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ćLz 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Γinfoczywiś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 Δ20- 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 Sjest 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.

Roy Simpson
źródło