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.

[...]
> Gdy uda się zbudować komputer 10^20 razy
> szybszy, to też powiesz żeby lepiej nie sprawdzać, bo problem stopu
> przeszkadza?

Co "żeby lepiej nie sprawdzać"? Jest całkiem dużo programów, które
sprawdzają, czy program zadany na wejściu się zatrzymuje (albo
weryfikują równoważną cechę) *mimo* problemu stopu. Problem stopu jest
wynikiem na analogicznym poziomie co twierdzenie Gödela o niezupełności.

>> Po drugie, model obliczeń nie ma tu nic do rzeczy. Może być sobie
>> maszyną Turinga, maszyną RAM, maszyną Lispową albo nietypowanym
>> wyrażeniem lambda; nierozstrzygalność zostaje dokładnie tym samym.
>> Natomiast nijak nie wiem, co _ty_ rozumiesz przez "model obliczeń",
>> skoro "zmieniasz" go zostając przy tym samym.
> Maszyna turinga może przyjąć nieskończoną ilość stanów. Komputer
> póki co ma ich ilość skończoną. Dlaczego uważasz ze to żadna różnica?

Co? Gdzie ja piszę o faktycznym komputerze?

>> A twoje rozumowanie jako dowód na "da się" jest jeszcze bardziej
>> bezużyteczne, bo trywialnym jest uzyskać znacznie mocniejsze
>> twierdzenie: zbiór programów, które się zakończą i które mieszczą się
>> w fizycznie wykonalnym komputerze, jest _językiem regularnym_, więc
>> wystarczy automat skończony i nie potrzeba maszyny Turinga. Jest tylko
>> jeden szkopuł: liczba stanów tego automatu będzie większa niż
>> astronomiczna.
> A jeden akapit wyżej pisałeś, że obojętne jest czy się weźmie MT czy
> komputer.

Gdzie tak napisałem?

> Nie wiem co chcesz właściwie powiedzieć. Nic co powiedziałem
> nie jest bezużyteczne.

Oczywiście że jest. Twoje twierdzenie o sprawdzalności programu jest
dużo słabsze, niż moje, a oba są użyteczne w dokładnie takim samym
stopniu, czyli wcale. Nie spodziewaj się znaczących wyników, gdy
bierzesz coś z fizycznymi ograniczeniami i pakujesz to w świat, który
tych ograniczeń nie ma. Ani to będzie użyteczne w świecie fizycznym, ani
to będzie coś nowego w świecie teoretycznym.

> W mniejszych problemach od dawna się to stosuje w
> praktyce i nikt nie marudzi że się nie uda bo problem stopu.

W mniejszych problemach stosuje się techniki zupełnie inne niż twoje
rozwiązanie problemu stopu. W ogóle prawie się nie dotyka tego
twierdzenia.

--
Secunia non olet.
Stanislaw Klekot

do góry

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

do góry

On 2016-09-26, M.M. <m...@g...com> wrote:
> 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?

Nieprawidłowo używasz między innymi terminów "problem stopu" (w tym
poście niżej; problem stopu to trochę co innego, niż próbujesz mi wmówić
w tej dyskusji) i "model obliczeń".

--
Secunia non olet.
Stanislaw Klekot

do góry

On Monday, September 26, 2016 at 5:09:27 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-26, M.M. <m...@g...com> wrote:
> > 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?
>
> Nieprawidłowo używasz między innymi terminów "problem stopu" (w tym
> poście niżej; problem stopu to trochę co innego, niż próbujesz mi wmówić
> w tej dyskusji) i "model obliczeń".
>

Dla mnie problem stopu to ustalenie czy dany ciąg instrukcji zakończy
się dla każdego zbioru danych wejściowych. Jaki tutaj widzisz błąd?
Na jednej taśmie jest ciąg bitów-odpowiedzi, na drugiej są ciągi
instrukcji - programy. Obie taśmy są wypełnione po nieskończoność,
stanowią program do ustalania czy program się zakończy czy nie. Jedyny
problem, to wypełnienie odpowiednimi wartościami tablicy z odpowiedzi.
Gdy program, dane wejściowe i dane robocze mają dowolnie duży, ale
ograniczony rozmiar, to oczywiście obie taśmy może zbudować trzecia
MT. Gdy nieskończony... myślę że też może, ale jest to trudniejsze.
W chwili obecnej nie jest znany taki algorytm.

Dla mnie nonsensem jest mówienie że problem stopu jest nierozstrzygalny,
tylko dlatego, że program o mniejszym rozmiarze nie może ustalić czy
program zakonczy się program o większym rozmiarze - a dowód tylko tyle
mówi.

Pozdrawiam

do góry

On 2016-09-26, 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?

>> Nieprawidłowo używasz między innymi terminów "problem stopu" (w tym
>> poście niżej; problem stopu to trochę co innego, niż próbujesz mi wmówić
>> w tej dyskusji) i "model obliczeń".

> Dla mnie problem stopu to [...]

I właśnie dlatego używasz tych terminów nieprawidłowo: twoje wyobrażenie
na temat znaczenia terminu nie zgadza się z tym, co faktycznie się pod
tym terminem kryje.

> [...] problem stopu to ustalenie czy dany ciąg instrukcji zakończy
> się dla każdego zbioru danych wejściowych. Jaki tutaj widzisz błąd?

W tym, że problem stopu to zadanie stworzenia *uniwersalnego* programu,
który rozstrzyga, czy zadany mu na wejściu program się zatrzyma.

Jeśli nagle ograniczasz maksymalny możliwy rozmiar programu wejściowego,
to w ogóle bez sensu jest mówić o problemie stopu na poziomie
teoretycznym, bo wtedy mamy do czynienia z czymś, co nie potrzebuje
maszyny Turinga/RAM/lambda ani gramatyki kontekstowej, ani nawet
bezkontekstowej: wystarczy wyrażenie regularne.

> Dla mnie nonsensem jest mówienie że problem stopu jest nierozstrzygalny,
> tylko dlatego, że program o mniejszym rozmiarze nie może ustalić czy
> program zakonczy się program o większym rozmiarze - a dowód tylko tyle
> mówi.

Jasne, najpierw podaj swoją własną, niezgodną z oryginałem definicję,
a potem twierdź, że problem jest rozstrzygalny.

Wiesz co? Ić stont być laikiem gdzie indziej.

--
Secunia non olet.
Stanislaw Klekot

do góry

On Monday, September 26, 2016 at 10:40:08 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-26, 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?
>
> >> Nieprawidłowo używasz między innymi terminów "problem stopu" (w tym
> >> poście niżej; problem stopu to trochę co innego, niż próbujesz mi wmówić
> >> w tej dyskusji) i "model obliczeń".
>
> > Dla mnie problem stopu to [...]
>
> I właśnie dlatego używasz tych terminów nieprawidłowo: twoje wyobrażenie
> na temat znaczenia terminu nie zgadza się z tym, co faktycznie się pod
> tym terminem kryje.
>
> > [...] problem stopu to ustalenie czy dany ciąg instrukcji zakończy
> > się dla każdego zbioru danych wejściowych. Jaki tutaj widzisz błąd?
>
> W tym, że problem stopu to zadanie stworzenia *uniwersalnego* programu,
> który rozstrzyga, czy zadany mu na wejściu program się zatrzyma.

Opowiem Ci kawał. Jeden facet pyta się drugiego:
- widzisz las?
- nie, bo drzewa mi zasłaniają.

Przecież to jest jedno i to samo!

> Jeśli nagle ograniczasz maksymalny możliwy rozmiar programu wejściowego,
Ależ nie ograniczyłem. Ograniczyłem tylko w przypadku gdy ciąg
odpowiedzi buduje MT. To był już kolejny akapit. MT może zbudować ciąg
odpowiedzi dla dowolnie dużego zbioru danych, byle ograniczonego, bo
zbioru danych o nieskończonym rozmiarze chociażby nie przekopiuje na
wejście programu w skończonym czasie.

Problem stopu jest rozstrzygalny, tylko nie istnieje program o skończonym
rozmiarze który by umiał rozstrzygnąć dla każdego programu. Program który
rozstrzyga dla każdego programu ma nieskończony rozmiar.

> to w ogóle bez sensu jest mówić o problemie stopu na poziomie
> teoretycznym, bo wtedy mamy do czynienia z czymś, co nie potrzebuje
> maszyny Turinga/RAM/lambda ani gramatyki kontekstowej, ani nawet
> bezkontekstowej: wystarczy wyrażenie regularne.
Jeszcze raz: nie ograniczyłem. Są dwa ciągi. Jeden ciąg programów, drugi
ciąg odpowiedzi. Tyle że niektóre odpowiedzi nie są jak na razie znane.


> > Dla mnie nonsensem jest mówienie że problem stopu jest nierozstrzygalny,
> > tylko dlatego, że program o mniejszym rozmiarze nie może ustalić czy
> > program zakonczy się program o większym rozmiarze - a dowód tylko tyle
> > mówi.
>
> Jasne, najpierw podaj swoją własną, niezgodną z oryginałem definicję,
> a potem twierdź, że problem jest rozstrzygalny.
>
> Wiesz co? Ić stont być laikiem gdzie indziej.
Sam jesteś laikiem, nie rozpoznałeś że to jest jedno i to samo.

do góry

On 2016-09-26, M.M. <m...@g...com> wrote:
>> > [...] problem stopu to ustalenie czy dany ciąg instrukcji zakończy
>> > się dla każdego zbioru danych wejściowych. Jaki tutaj widzisz błąd?
>>
>> W tym, że problem stopu to zadanie stworzenia *uniwersalnego* programu,
>> który rozstrzyga, czy zadany mu na wejściu program się zatrzyma.
>
> Opowiem Ci kawał. Jeden facet pyta się drugiego:
> - widzisz las?
> - nie, bo drzewa mi zasłaniają.
>
> Przecież to jest jedno i to samo!

Otóż nie. Ty chcesz ograniczać długość danych wejściowych i się
awanturujesz, że przecież to wykonalne. Problem stopu nie na tym polega.

>> Jeśli nagle ograniczasz maksymalny możliwy rozmiar programu wejściowego,
> Ależ nie ograniczyłem.

O? To nie bzdurzyłeś o uruchamianiu na komputerze nieograniczonym
jedynie programów, które się zmieszczą na rzeczywistym komputerze (czyli
są ograniczone przez, powiedzmy, 1TB kodu)?

> Problem stopu jest rozstrzygalny, tylko nie istnieje program o skończonym
> rozmiarze który by umiał rozstrzygnąć dla każdego programu. Program który
> rozstrzyga dla każdego programu ma nieskończony rozmiar.

O widzisz, czyli nagle mamy problem rozstrzygalny, którego jednak się
nie da rozstrzygnąć? Cieszę się, że przynajmniej w tej drugiej części
jednak się zgadzamy.

--
Secunia non olet.
Stanislaw Klekot

do góry

On Tuesday, September 27, 2016 at 2:04:48 AM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-26, M.M. <m...@g...com> wrote:
> >> > [...] problem stopu to ustalenie czy dany ciąg instrukcji zakończy
> >> > się dla każdego zbioru danych wejściowych. Jaki tutaj widzisz błąd?
> >>
> >> W tym, że problem stopu to zadanie stworzenia *uniwersalnego* programu,
> >> który rozstrzyga, czy zadany mu na wejściu program się zatrzyma.
> >
> > Opowiem Ci kawał. Jeden facet pyta się drugiego:
> > - widzisz las?
> > - nie, bo drzewa mi zasłaniają.
> >
> > Przecież to jest jedno i to samo!
>
> Otóż nie. Ty chcesz ograniczać długość danych wejściowych i się
> awanturujesz, że przecież to wykonalne. Problem stopu nie na tym polega.
Tam były właśnie dwa akapity. Jeden o tym że istnieje program który
rozstrzyga problem stopu dla każdego programu, a drugi o tym, że MT
generuje taki program. Nie zrozumiałeś i myślisz że coś mylę.


>
> >> Jeśli nagle ograniczasz maksymalny możliwy rozmiar programu wejściowego,
> > Ależ nie ograniczyłem.
>
> O? To nie bzdurzyłeś o uruchamianiu na komputerze nieograniczonym
> jedynie programów, które się zmieszczą na rzeczywistym komputerze (czyli
> są ograniczone przez, powiedzmy, 1TB kodu)?
Nigdy o niczym nie bzdurzyłem.


>
> > Problem stopu jest rozstrzygalny, tylko nie istnieje program o skończonym
> > rozmiarze który by umiał rozstrzygnąć dla każdego programu. Program który
> > rozstrzyga dla każdego programu ma nieskończony rozmiar.
>
> O widzisz, czyli nagle mamy problem rozstrzygalny, którego jednak się
> nie da rozstrzygnąć? Cieszę się, że przynajmniej w tej drugiej części
> jednak się zgadzamy.
Nie zgadzamy się, bo problem stopu na MT jest rozstrzygalny.

do góry

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.
A formalniej, istnienie takiej uniwersalnej procedury
prowadzi do paradoksu (fałszu). A wiec któreś z założeń
jest nieprawdziwe. Nie założyliśmy za wiele, więc albo
matematyka się wali, albo załozenie, że procedura stop
istenije, jest fałszywe.

pzdr
bartekltg

do góry

W dniu wtorek, 27 września 2016 09:04:18 UTC+2 użytkownik bartekltg napisał:
> On 27.09.2016 02:22, M.M. wrote:
> > Nie zgadzamy się, bo problem stopu na MT jest rozstrzygalny.
[...]
> Jakby nie patrzeć, z każdej strony dupa.
> A formalniej, istnienie takiej uniwersalnej procedury
> prowadzi do paradoksu (fałszu). A wiec któreś z założeń
> jest nieprawdziwe. Nie założyliśmy za wiele, więc albo
> matematyka się wali, albo załozenie, że procedura stop
> istenije, jest fałszywe.

Tym niemniej, konstrukcja, którą przedstawił M.M. (która w istocie
nie dotyczy problemu stopu), wydaje się analogiczna do teorii typów,
będącej jedną z propozycji rozwiązania Paradoksu Russella
(o strukturze analogicznej do problemu stopu).

Wydaje się, że tym, czego w istocie dowodzi przedstawiony przez
Ciebie argument, jest to, że logika dwuwartościowa nie jest
dość bogata do wyrażania naszych intuicji dotyczących programów
komputerowych -- bo przecież my jako ludzie nie mamy problemu
ze zrozumieniem źródła sprzeczności w tym dowodzie. Mianowicie
dowód ten mówi nam, że pewne programy, które mają explicite
rozstrzygać o swoich własnych właściwościach, mogą być kłopotliwe
w analize. (Oczywiście będą również takie, które bez problemu
rozstrzygają o pewnych swoich właściwościach)

Oczywiście temat jest bardzo słynny i szeroko dyskutowany,
ale rodzi następujące pytania (gdyby ktoś znał albo umiał
wymyślić na nie odpowiedzi, prosiłbym o ich tu przedstawienie):
- czy jeżeli zawęzimy problem stopu tylko do programów, które
nie odnoszą się do samych siebie, to czy wówczas staje
się rozstrzygalny? czy może też istnieje jakiś argument,
w którym nie używa się samoodnośnych programów, a z którego
również wynika nierozwiązywalność problemu stopu?

- czy istnieje jakaś systematyczna procedura rozpoznawania
programów, które będą popadały w ów paradoks zatrzymywalności?

do góry