On Tuesday, September 27, 2016 at 9:04:18 AM UTC+2, bartekltg wrote:
> On 27.09.2016 02:22, M.M. wrote:
> > Nie zgadzamy się, bo problem stopu na MT jest rozstrzygalny.
>
> Heh. Jeszcze raz, czego nie rozumiesz w dowodzie na
> nierozstrzygalność problemu stopu na kompie z nieskończoną pamięcią?
>
> Mamy procedurę stop:
>
> stop(program)
>
> zwraca ona true, jeśli program zakończy się, false w p.p.
>
> Procedura stop jest w tej chwili ustalona. Zapisana konkretna liość
> bitów, koniec, ma rozwiązać każdy problem.
>
> Kontrujemy program:
>
> test(X)
> if (stop(X)) //jeśli program X się nie zapętla
> for(;;); //zapętlij się
>
>
>
> Odpalam test(test)
>
> Zapętli się czy nie?
>
> Jeśli twierdzisz, że się zapętli, to
> stop(test)
> wzróci w skończonym czasie false.
> wiec test się zapętli na for(;;)
> Sprzecznosć.
>
> Jeśli twierdzisz, żę się nie zapętli, to
> stop(test)
> w skończonym czasie zwróci false.
> Program wykonał stop(test), sprawdził warunek
> i się zakończył.
> Sprzeczność.
>
> Jakby nie patrzeć, z każdej strony dupa.

Zgadza się, od jakiś 10-15 lat rozumiem ten dowód i się
z nim nie kłócę. Chodzi tylko o to, że jest budowany w
tym dowodzie program o większym rozmiarze od programu
który wykona test-stop. Takiego programu nie ma i
dowód w tym sensie jest poprawny - ale to jest
szczególny przypadek.

Jest to szczególny przypadek, bo program który rozstrzyga
może mieć nieskończony rozmiar. Nazwijmy ten program o
nieskończonym rozmiarze programem X. Program X dla
każdego programu Y o skończonym rozmiarze w skończonym
czasie ustali poprawnie czy program Y się zatrzyma czy
nie dla dowolnego zestawu danych wejściowych. Program X
teoretycznie istnieje, tylko w praktyce nikt nie umie
go (w kompletnej wersji) napisać. Jeśli istnieje program
na MT który rozstrzyga poprawnie problem stopu w skończonym
czasie, to ogólnie problem stopu jest rozstrzygalny.

> A formalniej, istnienie takiej uniwersalnej procedury
> prowadzi do paradoksu (fałszu).
Jak pisałem wyżej, tylko w przypadku szczególnym, gdy
procedura ma np. skończony lub zbyt mały rozmiar. W
przypadku ogólnym nie ma takiego paradoksu.


> A wiec któreś z założeń jest nieprawdziwe. Nie założyliśmy
> za wiele,
No jak to nie za wiele? Założyliśmy że procedura testowa
jest większa od procedury testującej. Tylko nie założyliśmy
tego jawnie, nikt w dowodzie nie mówi: załóżmy że procedura
testowana jest większa od testującej. Proszę Cię bardzo,
wykonaj dowód na odwrotnym przypadku, czyli gdy procedura
testująca ma znacznie większy rozmiar niż testowana.

> więc albo
> matematyka się wali, albo załozenie, że procedura stop
> istenije, jest fałszywe.
No właśnie jest jeszcze jedno założenie w dowodzie: procedura
testowana jest większa od testującej.

Pozdrawiam