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

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

Nie są „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.

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 . Przykłady takich problemów (gdzie jest funkcją częściowego obliczenia, a jest zestawem wyliczalnym obliczalnie): $0'$ $\Sigma^0_1$ $\phi_n$ $n$ $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ $n$

to -kompletne. $\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$ $\Sigma^0_2$
to -kompletne. $\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ $\Pi^0_2$
$\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ to . $\Sigma^0_3$

Ż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? $\varphi_n$ $n$ $n$

[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

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,

@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,

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,

\bar{H A L T}

$\overline{HALT}$

{< M, w >: M doesn't halt on w}

$\{<M,w>: \text{M doesn't halt on w} \}$

@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,