-
Data: 2016-09-25 23:03:27
Temat: Re: Testy losowości liczb
Od: "Stachu 'Dozzie' K." <d...@g...eat.some.screws.spammer.invalid> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 26.09.16 00:53 M.M.
- 26.09.16 11:02 Stachu 'Dozzie' K.
- 26.09.16 16:19 M.M.
- 26.09.16 17:09 Stachu 'Dozzie' K.
- 26.09.16 21:27 M.M.
- 26.09.16 22:40 Stachu 'Dozzie' K.
- 26.09.16 23:07 M.M.
- 27.09.16 02:04 Stachu 'Dozzie' K.
- 27.09.16 02:22 M.M.
- 27.09.16 09:04 bartekltg
- 27.09.16 12:41 g...@g...com
- 27.09.16 18:11 M.M.
- 27.09.16 18:25 M.M.
- 27.09.16 19:06 bartekltg
- 27.09.16 19:16 M.M.
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-10 wyobrazcie sobie ze
- 2024-06-10 malowanie samochodu
- 2024-06-10 News from Poland
- 2024-06-10 Czy na pewno będą CŁA na chińskie samochody?
- 2024-06-09 Dlaczego w Polsce sie nic nie udaje, na przykładzie niebieskiego lasera a teraz perskowitów
- 2024-06-09 Dlaczego w Polsce sie nic nie udaje, na przykładzie niebieskiego lasera a teraz perskowitów
- 2024-06-09 Wykrywanie przerwy w długim przewodzie zakopanym w ziemi.
- 2024-06-09 Czemu news.chmurka.nwt jest taki wolny?
- 2024-06-11 Funbox 3.0 zakres adresów DHCP
- 2024-06-11 Re: Funbox 3.0 zakres adresów DHCP
- 2024-06-09 Miernik szybkości netu
- 2024-06-11 Panele PV w pionie (prawie).
- 2024-06-11 czy ta grupa żyje?
- 2024-06-11 Warszawa => Senior React Native Developer <=
- 2024-06-11 Gdańsk => Kierownik Działu Spedycji Międzynarodowej <=