Jaka jest najmniejsza maszyna Turinga, w której nie wiadomo, czy się zatrzymuje?

31

Wiem, że problem zatrzymania jest ogólnie nierozstrzygalny, ale niektóre maszyny Turinga oczywiście zatrzymują się, a niektóre oczywiście nie. Która ze wszystkich możliwych maszyn Turinga jest najmniejsza, w której nikt nie ma dowodu, czy się zatrzymuje?

halting-problem

— Aaron
źródło

10

Odpowiedź zależy od specyfiki modelu maszyny (liczba symboli itp.). Zgodnie z artykułem Wikipedii o Busy Beaver istnieje 2-symbolowa 5-cio osobowa maszyna, która nie jest znana, czy się zatrzyma, czy nie.

— Kaveh

1

Zauważ, że pytanie Aarona nie dotyczy rozstrzygalności danego języka, ale tak naprawdę istnienia dowodu na zatrzymanie określonej maszyny Turinga. W przypadku każdej maszyny Turinga „jej” problem z zatrzymaniem (niezależnie od tego, czy ta maszyna zatrzymuje się na pustym wejściu) jest „rozstrzygalny”: jest to Tak lub Nie, a oba języki {Tak} i {Nie} są rozstrzygalne. Różni się to bardzo od tego, czy ktoś ma dowód, że maszyna się zatrzymuje, czy nie. Aaron, jeśli mam na myśli „co jest najmniejszą

takie, że język

zatrzymuje się

jest nierozstrzygalny,” Czy możesz edytować swoje pytanie?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

— Michaël Cadilhac

1

@ MichaëlCadilhac Problem zatrzymania jest zwykle interpretowany jako: „Biorąc pod uwagę maszynę

i wejście

, czy

zatrzymuje się na wejście

?” nie „Biorąc pod uwagę maszynę

, czy

zatrzymuje się dla wszystkich danych wejściowych?”

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

— David Richerby

@DavidRicherby: Dla mnie problemem zatrzymania jest język maszyny (kodów), który zatrzymuje się na pustych danych wejściowych. Jeśli nie jest to zamierzone znaczenie tutaj, myślę, że należy określić, aby rozproszyć możliwe (ok, moje) zamieszanie.

— Michaël Cadilhac

wiele sposobów badania problemu jest poprawnych i powiązanych ze sobą, a wyróżnienie ich jest subtelne, czego nie zadał pytający.

— vzn

38

Największe maszyny Turinga, dla których można rozwiązać problem zatrzymania, to:

$TM(2,3), TM(2,2), TM(3,2)$ $TM(k,l)$ $k$ $l$

$TM(2,4)$ $TM(3,3)$

$TM(4,2)$

Komentarz Kaveha i odpowiedź Mohammada są poprawne, więc w celu formalnej definicji standardowych / niestandardowych maszyn Turinga zastosowanych w tego rodzaju wynikach zobacz Turlough Neary i Damien Woods pracują na małych uniwersalnych maszynach Turinga, np . Złożoność małych uniwersalnych maszyn Turinga: ankieta (zasady TM 110 są mało uniwersalne).

— Marzio De Biasi
źródło

2

T M (4, 2)

$TM(4, 2)$

2

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$

32

Chciałbym dodać, że istnieje kilka maszyn Turinga, dla których problem zatrzymania jest niezależny od ZFC.

Na przykład weź maszynę Turinga, która szuka dowodu sprzeczności w ZFC. Zatem, jeśli ZFC jest spójne, nie zatrzyma się, ale nie można tego udowodnić w ZFC (z powodu drugiego twierdzenia Gödela o drugiej niepełności).

Więc nie chodzi tylko o to, że nie znalazłem jeszcze dowodu, czasem dowody nawet nie istnieją.

— Denis
źródło

ZFC? Co oznacza ZFC? Po prostu nie mogę tego zrozumieć na podstawie kontekstu.

— Acapulco

7

@Acapulco lmgtfy.com/?q=zfc&l=1

— Sasho Nikolov

Lol! dobrze. Dostałem. Touchè. Nie sądziłem, że będą to inicjały, które odniosą się natychmiast i w sposób unikalny do tego tematu. W każdym razie nie wydaje mi się, że dodanie grzecznościowego „ZFC (teoria mnogości Zermelo – Fraenkela)” za pierwszym razem jest bolesne, aby uniknąć dwuznaczności, jeśli tak jest? :)

— Acapulco

16

@Acapulco, zobacz przewodnik i centrum pomocy . Każdy teoretyczny informatyk wiedziałby, co oznacza ZFC, więc tak naprawdę nie ma potrzeby wyjaśniania.

— Kaveh

1

2

$2$

5

Nikt nie ma dowodu na to, czy Universal Turing zatrzyma się czy nie. W rzeczywistości taki dowód jest niemożliwy z powodu nierozstrzygalności problemu Haltinga. Najmniejsza jest 2-state 3-symbol uniwersalny Turinga maszyna, która została znaleziona przez Alex Smith za który otrzymał nagrodę w wysokości $ 25.000.

— Mohammad Al-Turkistany
źródło

4

Należy jednak zauważyć, że zgodnie z cytowaną stroną Wikipedii dowód uniwersalności jest kwestionowany. Ponadto nie jest to standardowy model maszyn Turinga: rzekomo uniwersalna maszyna nie ma stanu zatrzymania, więc nie może symulować żadnej maszyny, która się zatrzymuje, przynajmniej w standardowym znaczeniu tego, co robi uniwersalna maszyna Turinga.

— David Richerby

2

@DavidRicherby: Myślę, że słabo- uniwersalność reguły 110 jest dość akceptowana: wymaga dwóch różnych słów powtórzonych po lewej i prawej stronie wejścia, a warunkiem zatrzymania jest wygenerowanie specjalnego szybowca (generowanego wtedy i tylko wtedy, gdy symulowana maszyna zatrzymuje się). Zobacz „Uniwersalność w elementarnych automatach komórkowych” Matthew Cooka.

— Marzio De Biasi

-4

niedokładnie sformułowane, ale uzasadnione pytanie ogólne, które można zbadać na kilka szczególnych sposobów technicznych. istnieje wiele „małych” maszyn mierzonych stanami / symbolami, w których zatrzymanie jest nieznane, ale żadna „najmniejsza” maszyna nie jest możliwa, chyba że ktoś wymyśli jakąś uzasadnioną / kwantyfikowalną metrykę złożoności bazy TM, która uwzględnia zarówno stany, jak i symbole (najwyraźniej jak dotąd nikt jej nie zaproponował).

$x \times y$ $x$ $y$

$x,y$

— vzn
źródło

2

Nie ma potrzeby ustanawiania metryki uwzględniającej symbole i stany. Kiedy na taśmie znajdują się dwa symbole, jasne jest, że problem zatrzymania jest nierozstrzygalny dla prawie wszystkich stanów - jak pamiętam, możliwe jest napisanie uniwersalnej TM z tylko pięcioma stanami. Gdybyśmy znali dokładną granicę rozstrzygalności, jestem pewien, że łatwo byłoby opisać tę granicę za pomocą par (# stanów, # symboli).

— David Richerby

badanie zajętego bobra rzeczywiście polega na znalezieniu dowodów na to, czy bazy TM zatrzymują się przy początkowej konfiguracji z małą liczbą stanów, symboli; istnieją rozstrzygalne przypadki. jeśli ktoś chce „najmniejszego” czegokolwiek, musi stworzyć precyzyjną miarę mierzącą „małą”. powyższy punkt jest taki, że metryka, która obejmuje tylko same stany lub symbole, może być uważana za wprowadzającą w błąd, o ile reprezentuje znaną granicę, która obejmuje obie (i maszyny, o których wiadomo, że nie są uniwersalne). granica nierozstrzygalności w tych badaniach nie jest wcale „łatwa” do określenia w kategoriach czegokolwiek, to jest jej podstawowa natura ....

— wer

1

2 \leq i \leq 4

$2\leq i\leq 4$

k_{i}

$k_i$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

— David Richerby

jak dotąd nikt nie zaproponował żadnych danych. żadna ważna granica w tym obszarze nie jest „trywialna do opisania” i można oczekiwać, że scenariusz byłby niemożliwy za pośrednictwem Rices thm. wydaje się to świadczyć o nieznajomości badań i cytowanej publikacji, która jest zainteresowana rozdzielczością danych wejściowych dla maszyn, które są mniejsze niż te, o których wiadomo, że są uniwersalne (i przypuszcza się, że nie są uniwersalne). twoje komentarze wydają się koncentrować na granicach uniwersalnych vs nieuniwersalnych maszyn, co nie jest tym samym, co granice zajętości bobra badane np. w cytowanych referencjach (zarówno powyżej, jak i Marzio).

— vzn

x

$x$

y

$y$

x

$x$

y

$y$