-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!news.nask.pl!news.nask.org.pl!news.unit0.net!weretis.net!feeder1.news.
weretis.net!news.solani.org!.POSTED!not-for-mail
From: "Stachu 'Dozzie' K." <d...@g...eat.some.screws.spammer.invalid>
Newsgroups: pl.comp.programming
Subject: Re: Testy losowości liczb
Date: Sun, 25 Sep 2016 21:03:27 +0000 (UTC)
Organization: solani.org
Lines: 46
Message-ID: <s...@j...net>
References: <ns1l8a$oh4$1@node1.news.atman.pl> <ns2paj$lu0$1@node2.news.atman.pl>
<ns2rle$o74$1@node2.news.atman.pl>
<6...@g...com>
<f...@g...com>
<a...@g...com>
<4...@g...com>
<d...@g...com>
<b...@g...com>
<5...@g...com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-2
Content-Transfer-Encoding: 8bit
X-Trace: solani.org 1474837407 13746
eJwFwQkBwDAIA0BLfIEih7XEv4TdwVPzViQyQNCgx9l73iNVvuGiMDbtum28rErJYOtaQ34lphEV
(25 Sep 2016 21:03:27 GMT)
X-Complaints-To: a...@n...solani.org
NNTP-Posting-Date: Sun, 25 Sep 2016 21:03:27 +0000 (UTC)
User-Agent: slrn/pre1.0.0-18 (Linux)
X-User-ID: eJwFwYEBwCAIA7CXhqMFzrEo/59ggp/GDifoGMyMLttdZ1XiWNBwMy2+kJpS2V6FYe3ePfUAKH
URpQ==
Cancel-Lock: sha1:ISMqzc3ZL63L7d7LvPY8ZWRKfIc=
X-NNTP-Posting-Host: eJwNycERACEIA8CWRELAcriM9F+Ct98Np1EJBhETc6NaQ0faZ2exsWf9vW8W2jNL
qAun3HWgBwvZEFE=
Xref: news-archive.icm.edu.pl pl.comp.programming:209672
[ ukryj 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
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- 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??
Najnowsze wątki
- 2025-03-15 China-Kraków => Key Account Manager IT <=
- 2025-03-14 Spalił się autobus :-)
- 2025-03-14 Policjanci z Piątku
- 2025-03-14 Lublin => JavaScript / Node / Fullstack Developer <=
- 2025-03-14 Warszawa => Account Manager - Sprzedaż Usług Rekrutacyjnych <=
- 2025-03-14 Gliwice => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-03-14 VAT-R Umowa najmu na adres zamieszkania
- 2025-03-14 Gliwice => IT Expert (Network Systems area) <=
- 2025-03-14 Warszawa => Junior Rekruter <=
- 2025-03-14 Wrocław => Konsultant wdrożeniowy Comarch XL/Optima (Księgowość i
- 2025-03-14 China-Kraków => Senior PHP Symfony Developer <=
- 2025-03-14 Żerniki => Dyspozytor Międzynarodowy <=
- 2025-03-13 Raspberry Pi 3 Model B+
- 2025-03-13 Kuchenka elektryczna
- 2025-03-12 test