Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #28850
| Newsgroups | pl.comp.programming |
|---|---|
| Date | 2016-09-26 07:19 -0700 |
| References | (8 earlier) <b4eb45e8-e705-4f5e-b7d5-0a212c0ae78e@googlegroups.com> <580540b5-1760-4904-9776-be9da718a59f@googlegroups.com> <slrnnugeug.9h3.dozzie@jarowit.net> <a69d8347-1d14-4426-8d2d-6efb3aeba440@googlegroups.com> <slrnnuhp3k.9h3.dozzie@jarowit.net> |
| Message-ID | <efd2f8cf-d52b-4dc0-a90c-0389cf5b85cb@googlegroups.com> (permalink) |
| Subject | Re: Testy losowości liczb |
| From | "M.M." <mmarszik@gmail.com> |
On Monday, September 26, 2016 at 11:03:00 AM UTC+2, Stachu 'Dozzie' K. wrote: > On 2016-09-25, M.M. <mmarszik@gmail.com> wrote: > >> W swoim rozumowaniu mieszasz ze sobą wiele rzeczy. > [...] > > Wydaje Ci się że coś mieszam. > > Nie "wydaje mi się", tylko "widzę jak używasz terminów". Podpowiedź: > nieprawidłowo. > [...] Co jest nieprawidłowego w stwierdzeniu: że istnieje algorytm sprawdzający w skończonym czasie czy dany program na komputerze zakończy się, czy nie? Poza tym też istnieje taki program na MT. W dowodzie nierozstrzygalności problemu stopu jest przeszmuglowane błędne założenie. Program buduje się przez osadzenie jednego programu w drugim, co oznacza, że dowód nie tyczy się wszystkich przypadków (nie jest ogólny), ale tylko tych, w których program o mniejszym rozmiarze testuje program o większym rozmiarze. Jest bardzo prosty algorytm rozstrzygający problem stopu na MT. Oto on: Na jednej maszynie mamy kolejne programy zbudowane z wszystkich kombinacji instrukcji, najpierw zbudowane z jednej instrukcji, potem z dwóch itd aż do nieskończoności. Szczególik: mamy symbol dodatkowy nie będący żadną instrukcją. Symbol dodatkowy rozdziela programy. Głowica przebiega programy i zlicza symbole dodatkowe aż znajdzie program/programy który nas interesuje. Na drugiej maszynie jest ciąg bitów: zer i jedynek. Gdy pierwsza maszyna ustali, że interesujący nas program ma numer N, to druga szuka bitu o numerze N. Gdy bit wynosi 0, to program z maszyny pierwszej dla przynajmniej jednego zestawu danych nie zatrzyma się, a gdy 1, to dla każdego zestawu zakończy się. Oczywiście nie umiem podać ciągu z drugiej maszyny, ale w tej chwili nie umiem też z podać 3 cyfry po przecinku w liczbie PI. Czy to że nie znam ustawienia bitów w tym programie, albo to, że ten program jest nieskończenie długi, uprawnia mnie do twierdzenia, że problem stopu jest nierozstrzygalny? No chyba nie? Co więcej. Powyższą parę maszyn turinga może budować inna MT, nie jest do tego potrzeba wyrocznia. Można podać algorytm. Pamiętamy, że dane niczym się nie różnią od programu. Generujemy kolejno wszystkie wariacje programów zbudowanych z jednej instrukcji, z dwóch instrukcji, itd. Symulujemy wykonanie każdego programu. W trakcie symulowania zapamiętujemy zakres adresów na jakich znajdowała się głowica. Jeśli głowica wyjdzie poza zakres instrukcji, to problem stopu danego programu utożsamiamy z odpowiednim programem o większym rozmiarze. Gdy nie wyjdzie poza zakres, to albo osiągnie ponownie stan który osiągnął wcześniej, albo osiągnie stop. Jeśli osiągnie stop, to program się zatrzymuje, jeśli osiągnie ponownie ten sam stan, to program się pętli w nieskończoność. W ten sposób jedna maszyna turinga może zapełnić taśmę dwóch innych maszyn. Na jednej maszynie zapisze ciąg programów, na drugiej zapisze ciąg bitów. Czyli nie dość że problem jest rozstrzygalny, to jeszcze program do rozstrzygania może napisać automat bez wyroczni! Budowanie będzie trwało nieskończenie długo, ale czemu się dziwić, przecież wypełniamy taśmę o nieskończonej długości. To co powszechnie uważa się za dowód nierozstrzygalności problemu stopu, dowodzi tylko tego, że program o mniejszym rozmiarze nie może rozstrzygać dla programów większych. Nic dziwnego, rozmiar programu do rozstrzygania rośnie wykładniczo względem ilości programów dla których ma rozstrzygać. Pozdrawiam
Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 00:16 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:32 +0200
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 11:12 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 02:54 -0700
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 14:00 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 05:17 -0700
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 19:27 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:45 -0700
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 13:35 +0200
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-24 05:12 -0700
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 14:18 +0200
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 13:38 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-24 13:56 +0200
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-24 14:09 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-24 14:36 +0200
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-23 03:19 -0700
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-23 13:55 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-23 10:47 -0700
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-23 18:06 -0700
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 10:15 -0700
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 11:25 -0700
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 11:48 -0700
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 12:36 -0700
Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-25 21:03 +0000
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-25 15:53 -0700
Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 09:02 +0000
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 07:19 -0700
Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 15:09 +0000
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 12:27 -0700
Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-26 20:40 +0000
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 14:07 -0700
Re: Testy losowości liczb "Stachu 'Dozzie' K." <dozzie@go.eat.some.screws.spammer.invalid> - 2016-09-27 00:04 +0000
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-26 17:22 -0700
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-27 09:04 +0200
Re: Testy losowości liczb godek.maciek@gmail.com - 2016-09-27 03:41 -0700
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 09:25 -0700
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 09:11 -0700
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-27 19:06 +0200
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-27 10:16 -0700
Re: Testy losowości liczb Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2016-09-28 09:55 +0200
Re: Testy losowości liczb "M.M." <mmarszik@gmail.com> - 2016-09-28 03:51 -0700
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-25 14:20 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 14:47 +0200
Re: Testy losowości liczb Borneq <borneq@antyspam.hidden.pl> - 2016-09-25 15:07 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 15:11 +0200
Re: Testy losowości liczb bartekltg <bartekltg@gmail.com> - 2016-09-25 14:20 +0200
csiph-web