Zatrzymanie problemu bez odniesienia

W przypadku problemu zatrzymania jesteśmy zainteresowani, czy istnieje maszyna Turinga $T$ która może stwierdzić, czy dana maszyna Turinga $M$ zatrzymuje się, czy nie na danym wejściu . Zwykle dowód zaczyna zakładać, że taki istnieje. Następnie rozważamy przypadek, w którym ograniczamy do samego , a następnie wyprowadzamy sprzeczność za pomocą wystąpienia argumentu przekątnego. Jestem zainteresowany, jak poszedłby dowód, gdyby dano nam obietnicę, że ? Co z obietnicą , gdzie jest funkcjonalnie równoważne ? $i$ $T$ $i$ $M$ $i \not = M$ $i \not = M^\prime$ $M^\prime$ $M$

computability undecidability halting-problem dzwonek
źródło

Podpowiedź: nawet jeśli

nie jest wymagane, aby poprawnie odpowiedzieć na pytania o sobie, a nawet o

„s równoważne do niego, możemy nadal karmić równoważny

i zobaczyć, co robi. Ponieważ nie można obliczyć, czy

jest równoważne

nie będzie w stanie powiedzieć, że ma coś równoważnego sobie.

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

M

$M$

Andrej Bauer,

@AndrejBauer Czy to tylko wskazówka, którą mi dałeś i że powinienem rozwiązać mój rzeczywisty problem za pomocą tej wskazówki? Jestem trochę zdezorientowany, ponieważ rozwiązujesz problem, mówiąc „nie wymagający”, gdzie w moim otoczeniu obiecuję, że

nie będzie karmiony równoważnym

. Zasadniczo chciałbym zobaczyć jakikolwiek „odnośnik”, który sprawia, że problemy są nierozstrzygalne. Uważano, że tak jest w przypadku logiki i niekompletności.

M

$M$

M^{'}

$M^\prime$

bellpeace,

Możesz złamać obietnicę i nakarmić

co chcesz. W każdym razie nie może powiedzieć, że złamałeś obietnicę. Jeśli uważasz, że to oszustwo, nakarmię

rzeczami, które nie są równoważne

ponieważ są one podobne do

ale wszystkie dane wejściowe są przesunięte o

lub inne.

M

$M$

M

$M$

M

$M$

M

$M$

1

$1$

Andrej Bauer,

W rzeczywistości twoje pytania nie są dobrze sformułowane. Powinieneś nakreślić rzeczywisty dowód, który masz na myśli, a następnie określić, czego dokładnie chcesz uniknąć. Nie sądzę, że masz na myśli

, ale coś innego.

i \neq M

$i \neq M$

Andrej Bauer,

Odpowiedzi:

Załóżmy, że HALTS to TM, która odczytuje dane wejściowe jako parę i , gdzie jest kodowaniem TM, a jest dowolnym wejściem do tej TM. $M$ $x$ $M$ $x$

Twoje pytanie brzmi, czy to, co by się stało, jeśli założyliśmy zatrzymuje rozwiązało problemu stopu dla wszystkich wejść takie, że nie jest kodowanie TM, który jest funkcjonalnym odpowiednikiem . $\langle M,x \rangle$ $x$ $M$

Twierdzę, że oznacza to sprzeczność. Wymyśliłem to na miejscu, dlatego z zadowoleniem przyjmuję wszelką krytykę mojego dowodu. Ideą dowodu jest to, że zamiast przekątnej czegoś na sobie, tworzymy dwie wzajemnie rekurencyjne TM, które zachowują się różnie na niektórych danych wejściowych (a zatem nie są funkcjonalnie równoważne), ale w przeciwnym razie powodują sprzeczności.

Niech i będą dwiema wzajemnie rekurencyjnymi bazami TM (co oznacza, że możemy symulować, drukować itp., Opis w programie i odwrotnie). Zauważ, że możemy tworzyć wzajemnie rekurencyjne bazy TM na podstawie twierdzenia o rekurencji. $D_1$ $D_2$ $D_2$ $D_1$

Zdefiniuj i w następujący sposób: na wejściu , jeśli (10 wybranych dowolnie), następnie akceptuje i pętle. (W związku z tym nie są funkcjonalnie równoważne). $D_1$ $D_2$ $x$ $|x| < 10$ $D_1$ $D_2$

Biorąc pod uwagę pomocą , określa do symulacji zatrzymywane na i zatrzymania, jeśli zatrzymanie lub pętli, jeśli pętli. $x$ $|x| \ge 10$ $D_1$ $\langle D_2, x \rangle$ $D_2$ $D_2$

Biorąc pod uwagę pomocą , określa symulować zatrzymywane na i uchwyt, gdy zatrzymanie lub wstrzymania, jeśli pętli. $x$ $|x| \ge 10$ $D_2$ $\langle D_1, x \rangle$ $D_1$ $D_1$

Następnie zauważ, że dla dowolnego z , (x) zatrzymuje się lub zapętla. Jeśli zatrzymuje się na wejściu x, to wiemy, że HALTS ( , x) ustaliło, że zatrzymuje się na wejściu x. Jednak zatrzymanie na wejściu x oznacza, że pętle HALTS ( , x). $x$ $|x| \ge 10$ $D_1$ $D_1$ $D_2$ $D_2$ $D_2$ $D_1$

Jeśli na wejściowych pętlach , sprzeczność zachodzi podobnie. $D_1$ $x$

Jest to sprzeczność, chyba że jest kodowaniem dla maszyny Turinga funkcjonalnie równoważnym z lub , w którym to przypadku HALTS ma niezdefiniowane zachowanie. Jednak wybrano dowolnie ze wszystkich ciągów o rozmiarze większym niż . Pozostaje więc pokazać, że istnieje maszyna Turinga z kodowaniem o rozmiarze większym niż 10, który zachowuje się inaczej niż i . Możemy zbudować taką maszynę w sposób trywialny. CO BYŁO DO OKAZANIA. $x$ $D_1$ $D_2$ $x$ $10$ $D_1$ $D_2$

Myśli?

Kurt Mueller
źródło

Dlaczego musisz upewnić się, że

nie są funkcjonalnie równoważne?

D_{1}

$D_1$

D_{2}

$D_2$

bellpeace

Myślę, że masz rację, że nie jest to konieczne. Mój pierwotny zamiarem było diagonalize na postojami (

)

⟨ D_{1}, D_{2} ⟩

$\langle D_1, D_2 \rangle$

Kurt Mueller

Bez tego dowód jest bardziej elegancki, ale i tak wygląda dla mnie dobrze i jest dokładnie tym, czego potrzebowałem.

bellpeace,

Nadal nie jesteś z lasu. Napotkasz ten sam problem, tylko teraz dać mu inny TM jako wejścia, gdzie wybrałeś być funkcjonalnie równoważny (powiedzmy dodać nową regułę do tak, że porusza otwarcia s są jeden krok w prawo, jeden krok w lewo, w przeciwnym razie nie wprowadzisz żadnych zmian). Nadal będziesz w sprzeczności. Możesz spróbować wyeliminować wszystkie TM, które są równoważne , ale to jest nierozstrzygalny zestaw. $M'$ $M'$ $M$ $M$ $M'$ $M$

Aktualizacja . Napraw schemat kodowania, w którym Oznacza opis w ramach tego schematu TM i załóżmy, że miałeś TM, gdzie $\langle\,M\,\rangle$ $M$ $H$

jest niezdefiniowane, gdy jest kodowaniem TM, która oblicza tę samą funkcję cząstkową co (tj. i są funkcjonalnie równoważne). $H(\langle\,M\,\rangle, x)$ $x$ $H$ $x$ $H$
Dla wszystkich innych danych wejściowych zwraca wartość true tylko wtedy, gdy zatrzymuje się. $H(\langle\,M\,\rangle, x)$ $M(x)$

Obecnie zwykła konstrukcja przekątna wciąż powoduje sprzeczność. Zdefiniuj TM przez $Q$

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

Oczywiście i są funkcjonalnie inequivalent, więc można pozwolić $Q$ $H$ I znajdź to $x=\langle\,Q\,\rangle$ Zatrzymanie wtedy i tylko wtedy, jeśli nie zatrzymać, więc nie mogą być takie TM . $Q(\langle\,Q\,\rangle)$ $H$

Rick Decker
źródło

I załóżmy, że mam obietnicę, że

nie jest TM funkcjonalnie równoważne

? Może mogę przedłużyć moje pytanie w PO?

i

$i$

M

$M$

bellpeace,

Załóżmy, że otrzymałeś taką obietnicę; Wiem, że nie można tego obliczyć. Zaktualizowałem PO.

bellpeace,

@bellpeace:

$\:$ Jak to w ogóle zdefiniujesz?

$\;\;\;\;$

Wejście: parę liczb

w taki sposób,

nie oznacza TM TM funkcjonalnie równoważne przedstawiony

. Wyjście:

jeśli

zatrzymuje się na

, w przeciwnym razie

. Czy można rozwiązać ten problem?

(M, i)

$(M, i)$

i

$i$

M

$M$

1

$1$

M

$M$

i

$i$

0

$0$

bellpeace

@RickyDemer Tak, dwie bazy TM są uważane za funkcjonalnie równoważne, jeśli obliczają tę samą funkcję częściową. Zauważ, że jak zauważył Andrey, że chociaż ustalenie, czy

są równoważne, jest nierozstrzygalne, nadal możemy rozważyć problem, w którym otrzymujemy obietnicę, że dwa wejściowe TMS nie są równoważne, tak jak to zilustrowałem powyżej.

M

$M$

M^{'}

$M^\prime$

bellpeace,