On Monday, September 26, 2016 at 11:03:00 AM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-25, M.M. <m...@g...com> wrote:
> >> W swoim rozumowaniu mieszasz ze sobą wiele rzeczy.
> [...]
> > Wydaje Ci się że coś mieszam.
>
> Nie "wydaje mi się", tylko "widzę jak używasz terminów". Podpowiedź:
> nieprawidłowo.
> [...]


Co jest nieprawidłowego w stwierdzeniu: że istnieje algorytm sprawdzający w
skończonym czasie czy dany program na komputerze zakończy się, czy nie?

Poza tym też istnieje taki program na MT. W dowodzie nierozstrzygalności
problemu stopu jest przeszmuglowane błędne założenie. Program buduje się
przez osadzenie jednego programu w drugim, co oznacza, że dowód nie tyczy
się wszystkich przypadków (nie jest ogólny), ale tylko tych, w których
program o mniejszym rozmiarze testuje program o większym rozmiarze.

Jest bardzo prosty algorytm rozstrzygający problem stopu na MT. Oto on:
Na jednej maszynie mamy kolejne programy zbudowane z wszystkich kombinacji
instrukcji, najpierw zbudowane z jednej instrukcji, potem z dwóch itd aż
do nieskończoności. Szczególik: mamy symbol dodatkowy nie będący żadną
instrukcją. Symbol dodatkowy rozdziela programy. Głowica przebiega programy i zlicza
symbole dodatkowe aż znajdzie program/programy który nas interesuje.
Na drugiej maszynie jest ciąg bitów: zer i jedynek. Gdy pierwsza maszyna
ustali, że interesujący nas program ma numer N, to druga szuka bitu o
numerze N. Gdy bit wynosi 0, to program z maszyny pierwszej dla
przynajmniej jednego zestawu danych nie zatrzyma się, a gdy 1, to dla
każdego zestawu zakończy się. Oczywiście nie umiem podać ciągu z drugiej
maszyny, ale w tej chwili nie umiem też z podać 3 cyfry po przecinku w liczbie
PI. Czy to że nie znam ustawienia bitów w tym programie, albo to, że ten
program jest nieskończenie długi, uprawnia mnie do twierdzenia, że problem
stopu jest nierozstrzygalny? No chyba nie?


Co więcej. Powyższą parę maszyn turinga może budować inna MT, nie jest do
tego potrzeba wyrocznia. Można podać algorytm. Pamiętamy, że dane niczym
się nie różnią od programu. Generujemy kolejno wszystkie wariacje programów
zbudowanych z jednej instrukcji, z dwóch instrukcji, itd. Symulujemy wykonanie
każdego programu. W trakcie symulowania zapamiętujemy zakres adresów na jakich
znajdowała się głowica. Jeśli głowica wyjdzie poza zakres instrukcji, to
problem stopu danego programu utożsamiamy z odpowiednim programem o większym
rozmiarze. Gdy nie wyjdzie poza zakres, to albo osiągnie ponownie stan który
osiągnął wcześniej, albo osiągnie stop. Jeśli osiągnie stop, to program się
zatrzymuje, jeśli osiągnie ponownie ten sam stan, to program się pętli w
nieskończoność. W ten sposób jedna maszyna turinga może zapełnić taśmę dwóch
innych maszyn. Na jednej maszynie zapisze ciąg programów, na drugiej zapisze
ciąg bitów. Czyli nie dość że problem jest rozstrzygalny, to jeszcze program
do rozstrzygania może napisać automat bez wyroczni! Budowanie będzie trwało
nieskończenie długo, ale czemu się dziwić, przecież wypełniamy taśmę o
nieskończonej długości.


To co powszechnie uważa się za dowód nierozstrzygalności problemu stopu,
dowodzi tylko tego, że program o mniejszym rozmiarze nie może rozstrzygać
dla programów większych. Nic dziwnego, rozmiar programu do rozstrzygania
rośnie wykładniczo względem ilości programów dla których ma rozstrzygać.

Pozdrawiam