Problem stopu zakłada że istnieje:
Program S, który dla każdego programu P i
danych D dla programu P, zawsze się zatrzymuje i:
1) zwraca TAK gdy program P się zatrzymuje dla danych D
2) zwraca NIE gdy program P się nie zatrzymuje dla danych D.

Wyobraźmy sobie przykładowy program S:
Pod zerowym adresem jest miejsce na odpowiedź.
Począwszy od pierwszego adresu do adresu NS są instrukcje
i dane programu S. Od adresu NS+1 do adresu NP są
instrukcje programu P, od adresu NP+1 do adresu ND są
dane programu D. Można napisać:
S = 0 | INST_S | INST_P | DATA_D [1]

Założenie jest takie, że program S analizuje przez skończoną
ilość czasu program P uruchomiony na danych D, następnie
pod adres 0 wpisuje odpowiedź TAK albo NIE i kończy swoje
działanie.

Przy pomocy programu S można napisać program T. Program T
rozpoznaje czy program S dla programu P i danych D=P programu
P, zwrócił TAK czy NIE. Jeśli program S zwrócił TAK, to program
T wpada w wieczną pętlę, jeśli program S zwrócił NIE, to program
T kończy swoje działanie.

Wyobraźmy sobie program T w pamięci:
T = INST_T | S = INST_T | 0 | INST_S | P | P [2]

Wg dowodu programowi T można podać samego siebie jako
parametr P, czyli T(T). Otóż jest to niemożliwe. Dlaczego?
Podstawmy do [2] T pod P
T = INST_T | S = INST_T | 0 | INST_S | T | T
Podstawienie takie wymagałoby, aby program T w zajmowanej
przez siebie pamięci miał swoje dwie kopie i jeszcze dodatkowe
instrukcje. Wynika z tego że dowód na nierozstrzygalność
problemu stopu pokazuje, że problem stopu nie jest rozstrzygalny,
ale na programie który nie może istnieć.

Co kończy dowód.

P.S
Dowód pokazuje że "dowód na nierozstrzygalność jest błędny"
natomiast nic nie mówi o tym, czy problem stopu jest rozstrzygalny
czy nie.

do góry

On Aug 19, 3:35 pm, Mariusz Marszałkowski <m...@g...com> wrote:

> Wyobraźmy sobie przykładowy program S:
> Pod zerowym adresem jest miejsce na odpowiedź.
> Począwszy od pierwszego adresu do adresu NS są instrukcje
> i dane programu S. Od adresu NS+1 do adresu NP są
> instrukcje programu P, od adresu NP+1 do adresu ND są
> dane programu D. Można napisać:
> S = 0 | INST_S | INST_P | DATA_D [1]

Program P nie jest częścią programu S. Program S dostaje treść
programu P jako swoje dane, ale te dane nie wchodzą w skład programu
S.

> Przy pomocy programu S można napisać program T. Program T
> rozpoznaje czy program S dla programu P i danych D=P programu
> P, zwrócił TAK czy NIE. Jeśli program S zwrócił TAK, to program
> T wpada w wieczną pętlę, jeśli program S zwrócił NIE, to program
> T kończy swoje działanie.
>
> Wyobraźmy sobie program T w pamięci:
> T = INST_T | S = INST_T | 0 | INST_S | P | P [2]

Również tutaj treść P nie jest częścią T, tylko danymi dla T. Zatem
T(T) nie ma dodatkowej kopii danych dla T.

do góry

On 19 Sie, 17:58, "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
wrote:
> On Aug 19, 3:35 pm, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Wyobraźmy sobie przykładowy program S:
> > Pod zerowym adresem jest miejsce na odpowiedź.
> > Począwszy od pierwszego adresu do adresu NS są instrukcje
> > i dane programu S. Od adresu NS+1 do adresu NP są
> > instrukcje programu P, od adresu NP+1 do adresu ND są
> > dane programu D. Można napisać:
> > S = 0 | INST_S | INST_P | DATA_D [1]
>
> Program P nie jest częścią programu S. Program S dostaje treść
> programu P jako swoje dane, ale te dane nie wchodzą w skład programu
> S.
Program niczym nie różni się od swoich danych. Wynika z tego, że jeśli
program
przedstawisz jako dwa rozłączne zbiory, np. jako zbiór instrukcji i
danych, to też
dojdzie do sytuacji w której program T jest równy sobie i jeszcze
czemuś.

Spróbujmy rozpisać:
S = {INST} i {DATA}
S = {INST_S} i {0 | {INST_P} i {DATA_D} }

T = {INST_T} i {DATA}
T = {INST_T} i {T}

Co kończy dowód, gdyż zbiór INST_T jest niepusty.
Pozdrawiam

do góry

On 19 Sie, 17:58, "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
wrote:
> Również tutaj treść P nie jest częścią T, tylko danymi dla T. Zatem
> T(T) nie ma dodatkowej kopii danych dla T.

Czyli błąd jest tylko formalny, powinno być T( INSTRUKCJE_T ), T(T)
jest
czymś niemożliwym.

Pozdrawiam

do góry