eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingDlaczego dowód na nierozstrzygalność problemu stopu jest błędny
Ilość wypowiedzi w tym wątku: 4

  • 1. Data: 2010-08-19 13:35:34
    Temat: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny
    Od: Mariusz Marszałkowski <m...@g...com>

    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.


  • 2. Data: 2010-08-19 15:58:51
    Temat: Re: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny
    Od: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>

    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.


  • 3. Data: 2010-08-19 16:46:57
    Temat: Re: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny
    Od: Mariusz Marszałkowski <m...@g...com>

    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


  • 4. Data: 2010-08-20 19:52:51
    Temat: Re: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny
    Od: Mariusz Marszałkowski <m...@g...com>

    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

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: