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).

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