-
X-Received: by 10.157.51.3 with SMTP id f3mr1805048otc.4.1474992706604; Tue, 27 Sep
2016 09:11:46 -0700 (PDT)
X-Received: by 10.157.51.3 with SMTP id f3mr1805048otc.4.1474992706604; Tue, 27 Sep
2016 09:11:46 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit
0.net!news.glorb.com!o21no568691itb.0!news-out.google.com!w143ni365itb.0!nntp.g
oogle.com!x192no5369630itb.0!postnews.google.com!glegroupsg2000goo.googlegroups
.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Tue, 27 Sep 2016 09:11:46 -0700 (PDT)
In-Reply-To: <nsd5lh$6dr$1@node1.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=77.254.35.87;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 77.254.35.87
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>
<s...@j...net>
<a...@g...com>
<s...@j...net>
<e...@g...com>
<s...@j...net>
<d...@g...com>
<s...@j...net>
<f...@g...com>
<s...@j...net>
<4...@g...com>
<nsd5lh$6dr$1@node1.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6...@g...com>
Subject: Re: Testy losowości liczb
From: "M.M." <m...@g...com>
Injection-Date: Tue, 27 Sep 2016 16:11:46 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:209691
[ ukryj nagłówki ]On Tuesday, September 27, 2016 at 9:04:18 AM UTC+2, bartekltg wrote:
> On 27.09.2016 02:22, M.M. wrote:
> > Nie zgadzamy się, bo problem stopu na MT jest rozstrzygalny.
>
> Heh. Jeszcze raz, czego nie rozumiesz w dowodzie na
> nierozstrzygalność problemu stopu na kompie z nieskończoną pamięcią?
>
> Mamy procedurę stop:
>
> stop(program)
>
> zwraca ona true, jeśli program zakończy się, false w p.p.
>
> Procedura stop jest w tej chwili ustalona. Zapisana konkretna liość
> bitów, koniec, ma rozwiązać każdy problem.
>
> Kontrujemy program:
>
> test(X)
> if (stop(X)) //jeśli program X się nie zapętla
> for(;;); //zapętlij się
>
>
>
> Odpalam test(test)
>
> Zapętli się czy nie?
>
> Jeśli twierdzisz, że się zapętli, to
> stop(test)
> wzróci w skończonym czasie false.
> wiec test się zapętli na for(;;)
> Sprzecznosć.
>
> Jeśli twierdzisz, żę się nie zapętli, to
> stop(test)
> w skończonym czasie zwróci false.
> Program wykonał stop(test), sprawdził warunek
> i się zakończył.
> Sprzeczność.
>
> Jakby nie patrzeć, z każdej strony dupa.
Zgadza się, od jakiś 10-15 lat rozumiem ten dowód i się
z nim nie kłócę. Chodzi tylko o to, że jest budowany w
tym dowodzie program o większym rozmiarze od programu
który wykona test-stop. Takiego programu nie ma i
dowód w tym sensie jest poprawny - ale to jest
szczególny przypadek.
Jest to szczególny przypadek, bo program który rozstrzyga
może mieć nieskończony rozmiar. Nazwijmy ten program o
nieskończonym rozmiarze programem X. Program X dla
każdego programu Y o skończonym rozmiarze w skończonym
czasie ustali poprawnie czy program Y się zatrzyma czy
nie dla dowolnego zestawu danych wejściowych. Program X
teoretycznie istnieje, tylko w praktyce nikt nie umie
go (w kompletnej wersji) napisać. Jeśli istnieje program
na MT który rozstrzyga poprawnie problem stopu w skończonym
czasie, to ogólnie problem stopu jest rozstrzygalny.
> A formalniej, istnienie takiej uniwersalnej procedury
> prowadzi do paradoksu (fałszu).
Jak pisałem wyżej, tylko w przypadku szczególnym, gdy
procedura ma np. skończony lub zbyt mały rozmiar. W
przypadku ogólnym nie ma takiego paradoksu.
> A wiec któreś z założeń jest nieprawdziwe. Nie założyliśmy
> za wiele,
No jak to nie za wiele? Założyliśmy że procedura testowa
jest większa od procedury testującej. Tylko nie założyliśmy
tego jawnie, nikt w dowodzie nie mówi: załóżmy że procedura
testowana jest większa od testującej. Proszę Cię bardzo,
wykonaj dowód na odwrotnym przypadku, czyli gdy procedura
testująca ma znacznie większy rozmiar niż testowana.
> więc albo
> matematyka się wali, albo załozenie, że procedura stop
> istenije, jest fałszywe.
No właśnie jest jeszcze jedno założenie w dowodzie: procedura
testowana jest większa od testującej.
Pozdrawiam
Następne wpisy z tego wątku
- 27.09.16 18:25 M.M.
- 27.09.16 19:06 bartekltg
- 27.09.16 19:16 M.M.
- 28.09.16 09:55 Tomasz Kaczanowski
- 28.09.16 12:51 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-05-16 Samo rozładowywanie baterii trakcyjnej w elektryku.
- 2024-05-16 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-05-16 Warszawa => Interactive/Experience Designer <=
- 2024-05-16 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-16 Zabrze => Junior HelpDesk <=
- 2024-05-16 Warszawa => Technical Lead ( (Java Background)) <=
- 2024-05-16 Szczecin => Senior DevOps Engineer <=
- 2024-05-16 Szczecin => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-16 Śledztwo bodnatury "jak wyrok"? ["likwidator" Polskiego Radia donosi]
- 2024-05-16 Citi... zmiany warunków umowy o kartę kredytową Citibank?
- 2024-05-16 prawo jazdy z Nepalu
- 2024-05-15 Mini Netykieta polskich grup i list dyskusyjnych
- 2024-05-15 Warszawa => Key Account Manager <=
- 2024-05-15 Millenium czyli DEBILE bankowości
- 2024-05-15 Warszawa => Frontend Developer - React <=