Czy są jakieś istniejące problemy, których nie można rozwiązać za pomocą wyroczni zatrzymującej?

11

Rozumiem, że większość problemów jest trywialna, jeśli dostępna jest wyrocznia zatrzymująca (lub, moim zdaniem, hiper-obliczenia). Jednak zastosowanie argumentu, który pokazuje, że problem zatrzymania jest niemożliwy dla maszyny Turinga, pokazuje również, że wyrocznia Turinga + nie może zdecydować o problemie zatrzymania dla wyroczni Turinga +. Czy istnieją jakieś rzeczywiste, praktyczne przykłady problemów nierozwiązywalnych przez wyrocznię zatrzymującą?

Uwaga: przez „wyrocznię” rozumiem wyrocznię dla standardowej maszyny Turinga, a nie TM z samą wyrocznią.

ike
źródło
2
Nie „arbitralnie” Problemy nierozstrzygalne, patrz na przykład tutaj . Nie wiem o „praktycznych” przykładach (które również nie pasują do wybranego tytułu); co może być dla ciebie „praktyczne”?
Raphael
Nie są wymyślone po prostu, aby odpowiedzieć na to pytanie. Przyznałem, że problem zatrzymania następnego poziomu nadal obowiązuje.
ike
Ponadto wszystkie języki, których nie można wyliczyć rekurencyjnie, nie podlegają redukcji do HALT. Przykłady obejmują FINITE, EMPTY, czy dwa CFG pochodzą z tego samego języka itp.

Odpowiedzi:

15

Wystarczy wziąć problem, którego stopień Turinga jest większy niż , czyli stopień Wyroczni Stwórczej. Pod względem hierarchii arytmetycznej chcesz problemów, które są powyżej Ď 0 1 . Przykłady takich problemów (gdzie ϕ n jest n-tą funkcją częściowego obliczenia, a W n = { k Nϕ n ( k )  jest zdefiniowany } jest n-tym zestawem wyliczalnym obliczalnie):0Σ10ϕnnW.n={kN.ϕn(k) definiuje}n

  • to Σ 0 2 -kompletne.{nN.φn kończy się na skończoną liczbę wejść}Σ2)0
  • to Π 0 2 -kompletne.{nN.φn jest funkcją całkowitą}Π2)0
  • Σ 0 3{nN.W.n jest zestawem obliczalnym} to .Σ30

Żadnego z nich nie można rozwiązać, nawet jeśli masz Wyrocznię Wyroczni. Rozważmy na przykład drugi przykład: „czy total?” Biorąc pod uwagę jaki sposób Wyrocznia pomagałaby nam zdecydować, czy maszyna Turinga zakodowana przez zatrzymuje się na każdym wejściu? n nφnnn


[Dodano 2014-06-03] Dla „praktycznego” aspektu tego wszystkiego, rozważ problem: programista napisał funkcję void charge_credit_card(int card_number, int amount)i chcielibyśmy wiedzieć, czy funkcja kończy się na wszystkich wejściach. Jest to niemożliwe , aby napisać kompilator, który może automatycznie sprawdzać to w ogóle. Co więcej, nawet jeśli pozwolimy kompilatorowi zadać nam pytania o formie „czy charge_credit_cardkończy się, gdy otrzyma dane wejściowe (k,m)?”, Nadal jest to niemożliwe.

Andrej Bauer
źródło
2
Powiedzenie „Nie rozumiem przykładu” bez wyjaśnienia, co Cię dezorientuje, nie jest produktywne. Czy przeczytałeś odpowiednie strony Wikipedii, na które wskazałem? Są one bezpośrednio związane z twoim pytaniem, więc pierwszą rzeczą, którą powinieneś odnieść, jest zapoznanie się z podstawowymi pojęciami.
Andrej Bauer,
1
@ike, przykład miał mieć nieskończoną ilość int, oczywiście. Czy naprawdę potrzebujesz mnie do pisania BigInt, czy może narzekasz, że pamięć komputera jest skończona?
Andrej Bauer,
1
Cokolwiek. Powiedziałem ci, jaka jest odpowiedź na twoje pytanie. Jeśli nie chcesz tego rozumieć w dobrej wierze, nie przejmuj się pytaniami.
Andrej Bauer,
2
H.ZAL.T.¯{<M.,w>:M nie zatrzymuje się na w}
1
@tAllan: powinieneś opublikować to jako odpowiedź. Uderza mnie to, co OP uważa za „praktyczne”, ale twój przykład jest z pewnością lepszy niż mój.
Andrej Bauer,