Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28818 > unrolled thread

Testy losowości liczb

Back to article view | Back to pl.comp.programming

Contents

  Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 00:16 +0200
    Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:32 +0200
      Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 11:12 +0200
        Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 02:54 -0700
          Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 14:00 +0200
            Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 05:17 -0700
              Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 19:27 +0200
                Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:45 -0700
                  Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 13:35 +0200
                    Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-24 05:12 -0700
                      Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 14:18 +0200
                  Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 13:38 +0200
                    Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-24 13:56 +0200
                      Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 14:09 +0200
                        Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-24 14:36 +0200
        Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-23 03:19 -0700
          Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 13:55 +0200
          Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:47 -0700
            Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-23 18:06 -0700
              Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 10:15 -0700
                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 11:25 -0700
                  Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 11:48 -0700
                    Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 12:36 -0700
                      Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-25 21:03 +0000
                        Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 15:53 -0700
                          Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 09:02 +0000
                            Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 07:19 -0700
                              Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 15:09 +0000
                                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 12:27 -0700
                                  Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 20:40 +0000
                                    Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 14:07 -0700
                                      Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-27 00:04 +0000
                                        Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 17:22 -0700
                                          Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-27 09:04 +0200
                                            Re: Testy losowości liczb godek.maciek@gmail.com - 2016-09-27 03:41 -0700
                                              Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 09:25 -0700
                                            Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 09:11 -0700
                                              Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-27 19:06 +0200
                                                Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 10:16 -0700
                                                  Re: Testy losowości liczb Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2016-09-28 09:55 +0200
                                                    Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-28 03:51 -0700
      Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-25 14:20 +0200
        Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 14:47 +0200
          Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-25 15:07 +0200
            Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 15:11 +0200
    Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 14:20 +0200

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#28843

On Sunday, September 25, 2016 at 7:15:06 PM UTC+2, bartekltg wrote:
> On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> > On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> > > 
> > > > Jest jeden test, którego żaden deterministyczny generator nie
> > > > przejdzie. 
> > > > 
> > > 
> > > 
> > > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów 
> > > nie jest to technicznie wykonalne;-)
> > > 
> > > pzdr
> > > bartekltg
> > 
> > Chodziło o to, że teoretycznie można. Teoretycznie każdy 
> > deterministyczny ciąg da się mocno skompresować. W praktyce 
> > jest to niewykonalne,  ponieważ trzaby sprawdzać kolejno 
> > wszystkie metody kompresji. Niemniej każdy deterministyczny
> > ciąg ma małą złożoność kołmogorowa.
> 
> jest znacznie gorzej,
> tu się okazuje, że nawet teoretycznie nie można ;-)
> 
> https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_Kolmogorov_complexity
> 
> " there is no program which takes a string s as input and produces 
> the integer K(s) as output."
> 
> Polecam dowod, bardzo ładny.

Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze 
zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
który zarówno jedno i drugie zadanie rozwiąże.  

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28844

On Sunday, September 25, 2016 at 8:25:34 PM UTC+2, M.M. wrote:
> On Sunday, September 25, 2016 at 7:15:06 PM UTC+2, bartekltg wrote:
> > On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> > > On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > > > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> > > > 
> > > > > Jest jeden test, którego żaden deterministyczny generator nie
> > > > > przejdzie. 
> > > > > 
> > > > 
> > > > 
> > > > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów 
> > > > nie jest to technicznie wykonalne;-)
> > > > 
> > > > pzdr
> > > > bartekltg
> > > 
> > > Chodziło o to, że teoretycznie można. Teoretycznie każdy 
> > > deterministyczny ciąg da się mocno skompresować. W praktyce 
> > > jest to niewykonalne,  ponieważ trzaby sprawdzać kolejno 
> > > wszystkie metody kompresji. Niemniej każdy deterministyczny
> > > ciąg ma małą złożoność kołmogorowa.
> > 
> > jest znacznie gorzej,
> > tu się okazuje, że nawet teoretycznie nie można ;-)
> > 
> > https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_Kolmogorov_complexity
> > 
> > " there is no program which takes a string s as input and produces 
> > the integer K(s) as output."
> > 
> > Polecam dowod, bardzo ładny.
> 
> Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze 
> zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
> który zarówno jedno i drugie zadanie rozwiąże.  


Hmmm. Pewien jesteś? 
Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>

Jakbym jednak ja się mylił, podrzuć mi ten algorytm rozwiązujący problem 
stopu na komputerze.

Bo ja bym sobie odpalił go na prostym programie:


for (bigint n=1;;n+=2){
  bigint aku=0;
  for (d=n-1;d>0;d--)
    if (n%d==0) aku+=d;
  if (aku==n) return n;
}

Bardzo bym chciał wiedzieć, czy ten programik się zatrzyma,
a skoro jest to wykonalne... ;-)

Zerknąłem jeszzce do dowodu na problem stopu. tam też nic
o modelu obliczeniowym nie ma. Żadnych turigów (którym zresztą
komputer jest) i podobnych pierdół. 

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28845

On Sunday, September 25, 2016 at 8:48:17 PM UTC+2, bartekltg wrote:
> On Sunday, September 25, 2016 at 8:25:34 PM UTC+2, M.M. wrote:
> > On Sunday, September 25, 2016 at 7:15:06 PM UTC+2, bartekltg wrote:
> > > On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> > > > On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > > > > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> > > > > 
> > > > > > Jest jeden test, którego żaden deterministyczny generator nie
> > > > > > przejdzie. 
> > > > > > 
> > > > > 
> > > > > 
> > > > > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów 
> > > > > nie jest to technicznie wykonalne;-)
> > > > > 
> > > > > pzdr
> > > > > bartekltg
> > > > 
> > > > Chodziło o to, że teoretycznie można. Teoretycznie każdy 
> > > > deterministyczny ciąg da się mocno skompresować. W praktyce 
> > > > jest to niewykonalne,  ponieważ trzaby sprawdzać kolejno 
> > > > wszystkie metody kompresji. Niemniej każdy deterministyczny
> > > > ciąg ma małą złożoność kołmogorowa.
> > > 
> > > jest znacznie gorzej,
> > > tu się okazuje, że nawet teoretycznie nie można ;-)
> > > 
> > > https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_Kolmogorov_complexity
> > > 
> > > " there is no program which takes a string s as input and produces 
> > > the integer K(s) as output."
> > > 
> > > Polecam dowod, bardzo ładny.
> > 
> > Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze 
> > zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
> > który zarówno jedno i drugie zadanie rozwiąże.  
> 
> 
> Hmmm. Pewien jesteś? 
> Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
> Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>
> 
> Jakbym jednak ja się mylił, podrzuć mi ten algorytm rozwiązujący problem 
> stopu na komputerze.
> 
> Bo ja bym sobie odpalił go na prostym programie:
> 
> 
> for (bigint n=1;;n+=2){
>   bigint aku=0;
>   for (d=n-1;d>0;d--)
>     if (n%d==0) aku+=d;
>   if (aku==n) return n;
> }
> 
> Bardzo bym chciał wiedzieć, czy ten programik się zatrzyma,
> a skoro jest to wykonalne... ;-)
> 
> Zerknąłem jeszzce do dowodu na problem stopu. tam też nic
> o modelu obliczeniowym nie ma. Żadnych turigów (którym zresztą
> komputer jest) i podobnych pierdół. 
> 
> pzdr
> bartekltg

Była rozmowa może z 10 lat temu w której podałem algorytm, myślałem że
też śledziłeś, widocznie coś pomyliłem. 

Generalnie osobiście nie lubię MT jako modelu obliczeń. MT ma
nieskończoną pamięć, komputery - nie. Jest to na tyle mylące, że potem 
pewne problemy uważa się za niemożliwe do wykonania, a tymczasem one są
możliwe, tylko wymagają koszmarnego nakładu obliczeń i/albo pamięci. 
Niemniej różnica pomiędzy możliwe a niemożliwe jest zasadnicza. Ludzie 
mają już wyryty kanion obok synapsy którą przepływa słowo 'nieobliczalność'. 
A tym czasem problem stopu na komputerze jest całkowicie rozstrzygalny i 
to banalnie prostym algorytmem, który przyśnił mi się po godzinie
zastanawiania, nie musiałem nawet sięgać do żadnych mądrych książek. MT
powoduje, że ludzie nie chcą się zastanowić nad prostym zadaniem, tylko 
ślepo wierzą że nie można - nie lubię MT.

Do rzeczy. Bierzemy jeden komputer. Osadzamy w jego pamięci dowolny 
program, np. implementację tego algorytmu który w poście wyżej 
podałeś. Na drugim komputerze monitorujemy wykonanie programu w
pierwszym komputerze. Monitorowanie polega na zrzucaniu wszystkich
stanów pierwszego komputera do pamięci komputera drugiego. Innymi
słowy w komputerze drugim zapamiętujemy wszystkie stany jakie 
kolejno pojawiają się w komputerze pierwszym. Jeśli program osiągnął 
stop, to wiadomo, kończy się. Jeśli jakikolwiek stan się powtórzył, to 
będzie się pętlił teoretycznie w nieskończoność, w praktyce do 
uszkodzenia/wyłączenia komputera.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28846

On 2016-09-25, M.M. <mmarszik@gmail.com> wrote:
[...]
>> > Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze 
>> > zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
>> > który zarówno jedno i drugie zadanie rozwiąże.  
>> 
>> 
>> Hmmm. Pewien jesteś? 
>> Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
>> Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>
[...]
> Generalnie osobiście nie lubię MT jako modelu obliczeń. MT ma
> nieskończoną pamięć, komputery - nie. Jest to na tyle mylące, że potem 
> pewne problemy uważa się za niemożliwe do wykonania, a tymczasem one są
> możliwe, tylko wymagają koszmarnego nakładu obliczeń i/albo pamięci. 
> Niemniej różnica pomiędzy możliwe a niemożliwe jest zasadnicza.

W swoim rozumowaniu mieszasz ze sobą wiele rzeczy.

Po pierwsze, twój algorytm, co to przyśnił ci się po godzinie
zastanawiania, to coś, co jest niewykonalne na gruncie fizyki
(potrzebuje więcej bitów pamięci niż wszechświat ma atomów), a operuje
na danych, które fizycznie wykonalne już są. Mieszanie rzeczy
praktycznie wykonalnych i teoretycznie wykonalnych (ale potrzebujących
zasobów nie do zdobycia na gruncie fizyki) daje de facto bezużyteczne
wyniki. Albo się trzymamy praktycznej wykonalności, albo mówimy
o granicach teoretycznych (pewnym wyjątkiem jest tu kryptografia, ale to
inna para kaloszy).

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.

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.

-- 
Secunia non olet.
Stanislaw Klekot

[toc] | [prev] | [next] | [standalone]

#28847

On Sunday, September 25, 2016 at 11:03:28 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-25, M.M. <mmarszik@gmail.com> wrote:
> [...]
> >> > Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze 
> >> > zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
> >> > który zarówno jedno i drugie zadanie rozwiąże.  
> >> 
> >> 
> >> Hmmm. Pewien jesteś? 
> >> Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
> >> Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>
> [...]
> > Generalnie osobiście nie lubię MT jako modelu obliczeń. MT ma
> > nieskończoną pamięć, komputery - nie. Jest to na tyle mylące, że potem 
> > pewne problemy uważa się za niemożliwe do wykonania, a tymczasem one są
> > możliwe, tylko wymagają koszmarnego nakładu obliczeń i/albo pamięci. 
> > Niemniej różnica pomiędzy możliwe a niemożliwe jest zasadnicza.
> 
> W swoim rozumowaniu mieszasz ze sobą wiele rzeczy.
> 
> Po pierwsze, twój algorytm, co to przyśnił ci się po godzinie
> zastanawiania, to coś, co jest niewykonalne na gruncie fizyki
> (potrzebuje więcej bitów pamięci niż wszechświat ma atomów), a operuje
> na danych, które fizycznie wykonalne już są. Mieszanie rzeczy
> praktycznie wykonalnych i teoretycznie wykonalnych (ale potrzebujących
> zasobów nie do zdobycia na gruncie fizyki) daje de facto bezużyteczne
> wyniki. Albo się trzymamy praktycznej wykonalności, albo mówimy
> o granicach teoretycznych (pewnym wyjątkiem jest tu kryptografia, ale to
> inna para kaloszy).
Wydaje Ci się że coś mieszam. To tak samo jakbyś napisał, że lepiej 
nie robić projektu collatz, bo fizyka na to nie pozawala. Super-komputery 
są coraz mocniejsze. Coraz więcej problemów dla coraz większych zbiorów 
danych można na super komputerach sprawdzać. Fizyka z roku na rok 
przeszkadza coraz mniej. Gdy uda się zbudować komputer 10^20 razy 
szybszy, to też powiesz żeby lepiej nie sprawdzać, bo problem stopu
przeszkadza? Niektóre problemy, właśnie dla ważnych danych z praktycznego
punktu widzenia, można sprawdzać. Często dla dużych wartości danych 
da się przeprowadzić dowód teoretyczny, a dla małych potrzebne są 
szybkie komputery - jedna metoda właśnie z drugą współgra. 



> 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?



> 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. Nie wiem co chcesz właściwie powiedzieć. Nic co powiedziałem
nie jest bezużyteczne. W mniejszych problemach od dawna się to stosuje w
praktyce i nikt nie marudzi że się nie uda bo problem stopu.


Nie wiem gdzie Ty widzisz mieszanie. Na MT problem stopu przeszkadza nawet
teoretycznie. Na komputerze problem stopu przeszkadza z powodów technicznych.
Proste, jasne, łatwe do udowodnienia stwierdzenie - nie wiem co naprawdę
chcesz powiedzieć, chyba doszukałeś się czegoś w moich slowach, czego nie
powiedziałem.


Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28848

On 2016-09-25, M.M. <mmarszik@gmail.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

[toc] | [prev] | [next] | [standalone]

#28850

On Monday, September 26, 2016 at 11:03:00 AM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-25, M.M. <mmarszik@gmail.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

[toc] | [prev] | [next] | [standalone]

#28851

On 2016-09-26, M.M. <mmarszik@gmail.com> wrote:
> On Monday, September 26, 2016 at 11:03:00 AM UTC+2, Stachu 'Dozzie' K. wrote:
>> On 2016-09-25, M.M. <mmarszik@gmail.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

[toc] | [prev] | [next] | [standalone]

#28855

On Monday, September 26, 2016 at 5:09:27 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-26, M.M. <mmarszik@gmail.com> wrote:
> > On Monday, September 26, 2016 at 11:03:00 AM UTC+2, Stachu 'Dozzie' K. wrote:
> >> On 2016-09-25, M.M. <mmarszik@gmail.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 

[toc] | [prev] | [next] | [standalone]

#28856

On 2016-09-26, M.M. <mmarszik@gmail.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

[toc] | [prev] | [next] | [standalone]

#28857

On Monday, September 26, 2016 at 10:40:08 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-26, M.M. <mmarszik@gmail.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.

[toc] | [prev] | [next] | [standalone]

#28858

On 2016-09-26, M.M. <mmarszik@gmail.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

[toc] | [prev] | [next] | [standalone]

#28859

On Tuesday, September 27, 2016 at 2:04:48 AM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-26, M.M. <mmarszik@gmail.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.

[toc] | [prev] | [next] | [standalone]

#28860

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

[toc] | [prev] | [next] | [standalone]

#28862

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?

[toc] | [prev] | [next] | [standalone]

#28866

On Tuesday, September 27, 2016 at 12:41:53 PM UTC+2, godek....@gmail.com wrote:
> 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).
Czy mógłbyś powiedzieć która konstrukcja? Bo było wiele w tym wątku.
Pewnie moja wina, bo niezbyt klarownie piszę i skaczę po zagadnieniach.
 

> 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)
To nie wynika z problemu logiki dwuwartościowej. Logika pięknie
tutaj działa i dowód jest poprawny. Chodzi o to, że logika tutaj
pokazuje nieco inną rzecz niż nierozstrzygalność problemu stopu,
a mianowicie pokazuje szczególny przypadek problemu stopu, gdy
są nałożone ograniczenia na rozmiary programów testowanych i testujących.



> 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? 
Jeśli procedura rozstrzygająca ma odpowiednio duży rozmiar względem
procedury rozstrzyganej, to oczywiście tak. Przy stałym lub jakoś
inaczej ograniczonym rozmiarze procedury rozstrzygającej - nie
słyszałem.


> 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?
Problem stopu jest ogólnie rozstrzygalny, ponieważ MT może udzielić 
odpowiedzi czy program się zatrzyma czy nie.


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


Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28865

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

[toc] | [prev] | [next] | [standalone]

#28867

On 27.09.2016 18:11, M.M. wrote:

>
> Jest to szczególny przypadek, bo program który rozstrzyga
> może mieć nieskończony rozmiar.

Nie może.


pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#28868

On Tuesday, September 27, 2016 at 7:06:39 PM UTC+2, bartekltg wrote:
> On 27.09.2016 18:11, M.M. wrote:
> 
> >
> > Jest to szczególny przypadek, bo program który rozstrzyga
> > może mieć nieskończony rozmiar.
> 
> Nie może.

Dlaczego nie może? Taśma jest nieskończona, to zmieści się program o
nieskończonym rozmiarze, czyli może.

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#28875

W dniu 2016-09-27 19:16, M.M. pisze:
> On Tuesday, September 27, 2016 at 7:06:39 PM UTC+2, bartekltg wrote:
>> On 27.09.2016 18:11, M.M. wrote:
>>
>>>
>>> Jest to szczególny przypadek, bo program który rozstrzyga
>>> może mieć nieskończony rozmiar.
>>
>> Nie może.
>
> Dlaczego nie może? Taśma jest nieskończona, to zmieści się program o
> nieskończonym rozmiarze, czyli może.

Aż przypomniał mi się stary dowcip, że IBM stworzył dysk o nieskończonej 
pojemności, pokazany będzie, jak tylko skończy się formatować.


-- 
Kaczus
http://kaczus.ppa.pl

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | pl.comp.programming

csiph-web