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