Czy istnieje niepełny model Turinga, którego problem zatrzymania jest nierozstrzygalny?

26

Nie mogę wymyślić żadnego takiego modelu, może jakiejś formy wypisanego rachunku lambda? jakiś elementarny automat komórkowy?

To prawie obaliłoby „zasadę równoważności obliczeniowej” Wolframa:

Prawie wszystkie procesy, które nie są oczywiście proste, można postrzegać jako obliczenia o podobnym stopniu zaawansowania

automata-theory computability turing-machines lambda-calculus universal-computation Diego de Estrada
źródło

Odpowiedzi:

18

Możesz łatwo budować sztuczne modele, które nie są kompletne w Turinga, ale problem zatrzymania ich jest nierozstrzygalny. Np. Weź wszystkie TM, które nie zatrzymują się na niczym innym niż .0

W odniesieniu do oświadczenia:

Nie można obalić stwierdzenia, które nie jest wystarczająco precyzyjne. Prawie żadne słowo w instrukcji nie jest dobrze zdefiniowane (proszę podać ich definicję, jeśli tak nie jest).

Kaveh
źródło
mmm, powiedzmy, że model jest kompletny Turinga i może symulować UTM.
Diego de Estrada
1
Myślę, że zasada równoważności Wolframa jest bliższa fizyce niż logice. Logicy wydają się lubić atakować z różnych powodów: nie jest to precyzyjne, nie zostało to udowodnione, możemy tak układać, aby było fałszywe itp. Ale w rzeczywistości Wolfram na swój sposób wskazuje na bardzo interesujący fakt dotyczący obliczeń , jak powstaje „w naturze”.
Andrej Bauer,
1
Nie wiem jak zbierać wiśnie, książka wydaje mi się dość obszerna, szczególnie te wszystkie notatki. Czy istnieje a priori powód, dla którego nie można zmieniać standardowych definicji? Mierzysz tutaj niewłaściwy miernik. Wolfram nie robi matematyki, a przynajmniej nie w tradycyjnym tego słowa znaczeniu.
Andrej Bauer,
4
@Andrej, moim głównym problemem jest to, że stwierdzenie jest tak niejasne, że nie rozumiem, w jaki sposób można dokonać jakichkolwiek przewidywalnych / możliwych do odrzucenia prognoz. I tak, jeśli ktoś zmienia standardowe definicje, aby móc zinterpretować coś, co nie byłoby wsparciem dla roszczenia jako wsparcia dla roszczenia, to uważam, że jest to problematyczne.
Kaveh
4
Oświadczenie jest niejasne, ale co z tego? To nie jest logika ani matematyka. Jest to obserwacja, poparta grubą książką pełną przykładów, że w naturze „systemy obliczeniowe” są albo trywialnie proste, albo bardzo wyrafinowane i „równoważne” sobie. Zamiast krytykować Wolframa za to, że nie mówi języka żartów o logice i matematyce, bardziej produktywne byłoby zobaczenie, że ma on rację, a następnie sformułowanie tego w dowolnym formalizmie, jakiego pragnie twoje serce. Ale oczywiście, jeśli twoje serce nie chce czegoś takiego, to nie zrobisz tego.
Andrej Bauer,
4

Jestem prawie pewien, że argument diagonalizacji dotyczy dowolnego modelu obliczeń, który:

  • może przedstawiać się jako ciąg, oraz
  • może symulować inną maszynę, biorąc pod uwagę powyższą reprezentację

Gdybyśmy mieli model, który naruszył jeden z powyższych warunków, jego moc obliczeniowa byłaby bardzo ograniczona.

Gabgoh
źródło
10
Musisz być w stanie skutecznie policzyć maszyny, symulować je i obliczyć jakąś funkcję za pomocą właściwości . Ale diagonalizacja pokaże tylko problem zatrzymania dla tego modelu, którego nie mogą rozwiązać maszyny w modelu, nie oznacza to, że będzie on nierozstrzygalny (przez maszyny Turinga). ∀x.f(x)≠x
Kaveh
2

Nie jestem pewien dokładnego związku, ale wydaje się, że jest to związane z twierdzeniem Friedberga-Muchnika (patrz tutaj ): istnieje zbiór, którego stopień Turinga jest mniejszy niż problem zatrzymania. Ten wynik odpowiedział na wpływowe pytanie Posta i doprowadził do wprowadzenia „metody pierwszeństwa” w obliczalności.

Super0
źródło
-2

Prawdopodobnie. Istnieje wiele problemów matematycznych, które prawdopodobnie obejmują niektóre z nich, które są nierozstrzygalne, tj. Odpowiedź brzmi „tak”, ale nie ma na to dowodów. Na przykład jako problem pojawia się problem Collatz 3x + 1. Lub pytanie, czy pi zawiera dowolnie długie ciągi kolejnych 9s. Każdy taki problem można uznać za „model obliczeń” przypuszczalnie znacznie mniej wydajny niż UTM, ale nadal byłoby nierozstrzygalne, czy „przestanie”, czy „zawsze przestanie”.

Warren D. Smith
źródło
Nie sądzę, aby to podejście mogło zadziałać. Zobacz: dla każdego takiego stałego stwierdzenia istnieje algorytm, który decyduje, czy jest on „prawdziwy”, czy „fałszywy” w skończonym czasie, nawet jeśli jest niezdecydowany w ZFC (zob .: en.wikipedia.org/wiki/Busy_beaver # Aplikacje ). Z drugiej strony, jeśli weźmie się pod uwagę model obliczeniowy, problem „biorąc pod uwagę stwierdzenie, zdecyduj, czy ma on dowód w ZFC”, myślę, że model ten jest kompletny w Turingu.
Diego de Estrada