On Sunday, September 25, 2016 at 11:03:28 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-25, M.M. <m...@g...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