Naprawdę generator liczb losowych: obliczanie Turinga?

Szukam ostatecznej odpowiedzi na pytanie, czy generowanie „prawdziwie losowych” liczb jest obliczalne przez Turinga. Nie wiem, jak to dokładnie sformułować. Pytanie StackExchange dotyczące „wydajnych algorytmów do generowania liczb losowych” jest bliskie odpowiedzi na moje pytanie. Charles Stewart mówi w swojej odpowiedzi: „To [losowości Martina-Löfa] nie może być wygenerowane przez maszynę”. Ross Snider mówi: „jakikolwiek deterministyczny proces (taki jak Turing / Register Machines) nie może wytworzyć„ filozoficznych ”lub„ prawdziwych ”liczb losowych”. Czy istnieje jasne i akceptowane pojęcie tego, co stanowi prawdziwie losowy generator liczb? A jeśli tak, to czy wiadomo, że nie można go obliczyć za pomocą maszyny Turinga?

Być może wystarczyłoby wskazanie mi odpowiedniej literatury. Dzięki za wszelką pomoc, którą możesz udzielić!

Edytować. Dzięki Ian i Aaron za kompetentne odpowiedzi! W tej dziedzinie jestem stosunkowo nieuczony i jestem wdzięczny za pomoc. Jeśli mogę nieco rozszerzyć pytanie w tym dodatku: Czy jest tak, że TM z dostępem do czystego źródła losowości (wyrocznia?) Może obliczyć funkcję, której klasyczna TM nie może?

Dołączam do dyskusji dość późno, ale postaram się odpowiedzieć na kilka pytań, które zostały zadane wcześniej.

Po pierwsze, jak zauważył Aaron Sterling, ważne jest, aby najpierw zdecydować, co rozumiemy przez „prawdziwie losowe” liczby, a zwłaszcza, jeśli patrzymy na rzeczy z perspektywy złożoności obliczeniowej lub obliczalności.

Argumentuję jednak, że w teorii złożoności ludzie są zainteresowani głównie pseudo- losowością i pseudo- losowymi generatorami, tj. Funkcjami od ciągów do ciągów, tak że rozkładu sekwencji wyjściowych nie można odróżnić od rozkładu równomiernego za pomocą wydajnego procesu (gdzie można wziąć pod uwagę kilka znaczeń wydajności , np. obliczalny czas policyjny, obwody wielomianowe itp.). Jest to piękny i bardzo aktywny obszar badawczy, ale myślę, że większość ludzi zgodzi się, że badane przez niego obiekty nie są naprawdę przypadkowe, wystarczy, że wyglądają po prostu losowo (stąd termin „pseudo”).

W teorii obliczeń pojawił się konsensus, który powinien być dobrym pojęciem „prawdziwej przypadkowości”, i faktycznie to właśnie dominowało pojęcie losowości Martina-Löfa (inne zostały zaproponowane i są interesujące do zbadania, ale nie ujawniają wszystkich ładne właściwości przypadkowości Martina-Löfa). Aby uprościć sprawy, rozważymy losowość nieskończonych sekwencji binarnych (inne obiekty, takie jak funkcje od ciągów do ciągów, można łatwo zakodować za pomocą takiej sekwencji).

Nieskończona sekwencja binarna jest losowa Martin-Löf, jeśli żaden proces obliczeniowy (nawet jeśli pozwalamy na obliczenie tego procesu w potrójnym czasie wykładniczym lub wyższym) nie może wykryć błędu losowości.$\alpha$

(1) Co rozumiemy przez „wadę losowości”? Ta część jest prosta: jest to zbiór miary 0, czyli właściwość, że niemal wszystkie sekwencje nie mają (tutaj mówimy o miary Lebesgue'a czyli środka, gdzie każdy bit ma prawdopodobieństwa być 0 niezależnie od wszystkich innych bitów). Przykładem takiej wady jest „posiadanie asymptotycznie 1/3 zer i 2/3 jedynek”, co narusza prawo wielkich liczb. Innym przykładem jest „na każde n pierwsze 2n bitów α są idealnie rozłożone (tyle zer, ile zer)”. W tym przypadku prawo wielkich liczb jest usatysfakcjonowane, ale nie centralne twierdzenie graniczne. Itd itd.$1/2$$0$$\alpha$
(2) W jaki sposób obliczalny proces może sprawdzić, czy sekwencja nie należy do określonego zestawu miary 0? Innymi słowy, jakie zestawy miary 0 można opisać obliczalnie? Właśnie o to chodzi w testach Martina-Löfa. Test Martin-Löf obliczeniowy jest procedura, która, ze względu an k computably wejściowego, (czyli przez maszynę z wejściem Turingowi ) generuje sekwencję łańcuchów w k , 0 , w k , 1 , ... taki sposób, że zestaw u K nieskończonych sekwencji począwszy od jednego z tych, w k , i ma środki najwyżej 2 - $k$$w_{k,0}$$w_{k,1}$$U_k$$w_{k,i}$$2^{-k}$(jeśli lubisz topologię, zwróć uwagę, że jest to otwarty zestaw w topologii produktu dla zestawu nieskończonych sekwencji binarnych). Następnie zestaw ma miarę 0 i jest nazywany zerowym Martin-Löf . Możemy teraz zdefiniować losowość Martina-Löfa, mówiąc, że nieskończona sekwencja binarna α jest losowa Martina-Löfa, jeśli nie należy do żadnego zerowego zestawu Martina-Löfa . $G=\bigcap_k U_k$$0$$\alpha$

Ta definicja może wydawać się techniczna, ale jest powszechnie akceptowana jako odpowiednia z kilku powodów:

• jest wystarczająco skuteczny, tzn. jego definicja obejmuje procesy obliczalne
• jest wystarczająco silny: każdą „prawie pewną” właściwość, którą można znaleźć w podręczniku teorii prawdopodobieństwa (prawo dużych liczb, prawo iterowanego logarytmu itp.), można przetestować za pomocą testu Martina-Löfa (chociaż czasem trudno to udowodnić)
• zostało niezależnie zaproponowane przez kilka osób posługujących się różnymi definicjami (w szczególności definicją Levina-Chaitina stosującą złożoność Kołmogorowa); a fakt, że wszystkie prowadzą do tej samej koncepcji, jest wskazówką, że powinno to być właściwe pojęcie (trochę podobne do pojęcia funkcji obliczalnej, którą można zdefiniować za pomocą maszyn Turinga, funkcji rekurencyjnych, rachunku lambda itp.)
• matematyczna teoria jest bardzo ładna! zobacz trzech doskonałych książek wstępem do Złożoność Kołmogorowa i jej zastosowań (Li i Vitanyi) Algorithmic przypadkowości i złożoności (Downey i Hirschfeldt) obliczalności i FORUMOWA (Nies).

Jak wygląda losowa sekwencja Martina-Löfa? Weź doskonale wyważoną monetę i zacznij ją rzucać. Przy każdym przerzuceniu napisz 0 dla głów i 1 dla ogonów. Kontynuuj do końca czasu. Tak wygląda sekwencja Martina-Löfa :-)

Wracając do początkowego pytania: czy istnieje obliczalny sposób na wygenerowanie losowej sekwencji Martina-Löfa? Intuicyjnie odpowiedź powinna brzmieć NIE , ponieważ jeśli możemy użyć obliczalnego procesu do wygenerowania sekwencji , to z pewnością możemy użyć obliczalnego procesu do opisania singletonu { α }, więc α nie jest losowy. Formalnie odbywa się to w następujący sposób. Załóżmy, że sekwencja α jest obliczalna. Rozważmy następujący test Martin-LOF: dla wszystkich k , tylko wyjście przedrostek k od alfa o długości k , i nic więcej. Ma to co najwyżej (a właściwie dokładnie) 2 - $\alpha$$\alpha$$\alpha$$\alpha$$k$$a_k$$\alpha$$k$$2^{-k}$, a przecięcie zbiorów jak w definicji wynosi dokładnie { α }. CO BYŁO DO OKAZANIA!!$U_k$${\alpha}$

W rzeczywistości losowa sekwencja Martina-Löfa jest nieporównywalna w znacznie silniejszym sensie: jeśli jakieś obliczenie wyroczni z wyrocznią β (która sama jest nieskończoną sekwencją binarną) może obliczyć α , to dla wszystkich n , n - O ( 1 ) bitów β są potrzebne do obliczenia pierwszych n bitów α (w rzeczywistości jest to charakterystyka losowości Martina-Löfa, która niestety jest rzadko podawana, jak ma to miejsce w literaturze).$\alpha$$\beta$$\alpha$$n$$n-O(1)$$\beta$$n$$\alpha$

Ok, teraz część „edytująca” pytania Józefa: Czy jest tak, że TM z dostępem do czystego źródła losowości (wyrocznia?) Może obliczyć funkcję, której nie potrafi klasyczna TM?

Z punktu widzenia obliczalności odpowiedź brzmi „tak i nie”. Jeśli otrzymasz dostęp do losowego źródła jako wyrocznia (gdzie wynik jest przedstawiany jako nieskończona sekwencja binarna), z prawdopodobieństwem 1 otrzymasz losową wyrocznię Martin-Löf, a jak widzieliśmy wcześniej, przypadek Martin-Löf oznacza brak obliczalny, więc wystarczy wyprowadzić samą wyrocznię! Lub jeśli chcesz funkcji , możesz wziąć pod uwagę funkcję f, która dla wszystkich n mówi, ile zer jest wśród pierwszych n bitów twojej wyroczni. Jeśli wyrocznia jest losowa Martin-Löf, tej funkcji nie da się obliczyć.$f: \mathbb{N} \rightarrow \mathbb{N}$$f$$n$$n$

Ale oczywiście można argumentować, że jest to oszustwo: w rzeczywistości dla innej wyroczni możemy uzyskać inną funkcję, więc istnieje problem braku powtarzalności. Stąd innym sposobem na zrozumienie twojego pytania jest: czy istnieje funkcja której nie można obliczyć, ale którą można „obliczyć z prawdopodobieństwem dodatnim”, w tym sensie, że istnieje maszyna Turinga z dostępem do losowej wyroczni, która: z prawdopodobieństwem dodatnim (nad wyrocznią) oblicza f . Odpowiedź brzmi „nie” z powodu twierdzenia Sacksa, którego dowód jest dość prosty. Właściwie odpowiedział na to głównie Robin Kothari: jeśli prawdopodobieństwo poprawności TM jest większe niż 1/2, wówczas można szukać wszystkich n we wszystkich możliwych obliczeniach Oracle z wejściem $f$$f$$n$$n$i znajdź wyniki, które otrzymają „większość głosów”, tj. które są wytwarzane przez zbiór wyroczni miar większych niż 1/2 (można to zrobić skutecznie). Argument rozciąga się nawet na mniejsze prawdopodobieństwa: załóżmy, że wyjścia TM mają prawdopodobieństwo ϵ > 0 . Według twierdzenia o gęstości Lebesgue'a istnieje łańcuch skończony σ, taki że jeśli poprawimy pierwsze bity wyroczni na dokładnie σ , a następnie uzyskamy losowo pozostałe bity, to obliczymy f z prawdopodobieństwem co najmniej 0,99. Przyjmując takie σ , możemy ponownie zastosować powyższy argument.$f$$\epsilon >0$$\sigma$$\sigma$$f$$\sigma$

Aby odpowiedzieć na twoje pytanie, należy (być może) wprowadzić rozróżnienie między „obliczaniem Turinga” a „obliczaniem efektywnym”. Jeśli zdefiniujemy „proces losowy” jako „proces, którego nie można przewidzieć, bez względu na to, jakie zasoby mamy”, i zdefiniujemy „proces deterministyczny” jako „proces przewidywalny, biorąc pod uwagę wkład i dostęp do (być może wielu) zasobów, „wtedy żadna funkcja obliczeniowa Turinga nie może być losowa, ponieważ gdybyśmy znali maszynę Turinga i ją symulowali, zawsze moglibyśmy przewidzieć wynik następnego„ eksperymentu ”procesu.

W tych ramach test Martin-Lof można postrzegać jako proces deterministyczny, a definicja losowej sekwencji jest dokładnie sekwencją, której zachowanie nie jest przewidywane przez żaden test Martin-Lof / proces obliczeniowy / deterministyczny Turinga.

Nasuwa to jednak pytanie: „Czy losowa sekwencja jest w rzeczywistości możliwa do obliczenia w prawdziwym życiu?” W rzeczywistości jest tu branża. Są publikowane płyty CD z miliardami losowych (?) Bitów, które są używane do przeprowadzania komputerowych symulacji układów fizycznych itp. Te płyty CD gwarantują, że ich sekwencje bitów przechodzą szereg testów Martina-Lofa. Książka „Drunkard's Walk: How Randomness rządzi naszym życiem” zawiera bardziej szczegółowe wyjaśnienie tego problemu pop-sci.

Nieistotny punkt: podoba mi się twoja kolumna. :-)

Intuicyjnie „losowy” oznacza „nieprzewidywalny”, a dowolną sekwencję wygenerowaną przez maszynę Turinga można przewidzieć, uruchamiając maszynę, więc maszyny Turinga nie mogą wytwarzać liczb „prawdziwie losowych”. Istnieje wiele formalnych definicji losowych sekwencji (losowość ma sens tylko wtedy, gdy długość łańcucha dochodzi do nieskończoności), z których wszystkie są zasadniczo równoważne. Być może najbardziej naturalną z nich jest losowość Martina-Lofa, co oznacza, że ​​sekwencja przechodzi wszystkie możliwe do obliczenia testy statystyczne na stochastyczność, oraz losowa Chaitina, co oznacza, że ​​wszystkie początkowe podsekwencje są nieściśliwe (a dokładniej, mają wysoką złożoność Kołmogorowa). W obu tych definicjach nie można obliczyć generowania losowych sekwencji i ich rozpoznawania. Zobacz książkę „Informacje i losowość:

Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu. Ponieważ, jak już wielokrotnie podkreślano, nie istnieje coś takiego jak liczba losowa - istnieją tylko metody tworzenia liczb losowych, a ścisła procedura arytmetyczna oczywiście nie jest taką metodą. - John von Neumann

Wygląda na to, że nikt nie odpowiedział na twoje uzupełnienie, więc spróbuję:

Jeśli mogę nieco rozszerzyć pytanie w tym dodatku: Czy jest tak, że TM z dostępem do czystego źródła losowości (wyrocznia?) Może obliczyć funkcję, której klasyczna TM nie może?

Spróbuję sprecyzować pytanie, a następnie odpowiem na nie. (Moja wersja może nie być tym, co masz na myśli, więc daj mi znać, jeśli nie jest).

Mamy deterministyczną bazę TM z dostępem do generatora liczb losowych. Ta TM oblicza teraz pewną funkcję (rzeczywistą funkcję, tj. Mapę deterministyczną z przestrzeni wejściowej do przestrzeni wyjściowej), wykorzystując w jakiś sposób generator liczb losowych.

Czy więc TM z dostępem do losowości może popełnić błąd? Jeśli nie, to DTM musi dać poprawną odpowiedź, bez względu na to, jakie losowe bity zostało dostarczone. W tym przypadku losowe bity są niepotrzebne, ponieważ można po prostu wziąć losowy ciąg o wartości 00000 ...

$f_i(x,r)$$f_i$$r$

Jeśli chodzi o twoje „pytanie edycyjne”: ma duże znaczenie, jeśli pytasz o obliczalność lub złożoność. Jeśli w TM istnieją granice złożoności, otrzymujesz tak zwany model losowej wyroczni . Jeśli TM może użyć dowolnie dużych, ale skończonych zasobów, to jesteś w świecie względnej losowości : istnieją hierarchie losowości wyroczni, podobnie jak stopni Turinga. (Punkt boczny: jedna z (nie) znanych krytyków Koblitza i Menzesa dotyczyła użycia modelu losowej wyroczni, więc twoje meta-pytanie dotyczy ostatnich debat akademickich.)

Wciąż próbuję zrozumieć twoje zmodyfikowane pytanie, szczególnie jakie ograniczenia nakładasz na TM. Więc chociaż ta odpowiedź może nie osiągnąć dokładnie tego, czego chcesz, być może pomoże to nieco zawęzić sytuację.

Wiemy, że istnieje bezwarunkowy wynik niemożności przybliżenia z czynnikiem podwykładniczym objętości ciała wypukłego deterministycznie (jest to stary wynik Bárány i Füredi ). W przeciwieństwie do tego możemy uzyskać FPRAS dla tego problemu za pomocą próbkowania. Czy to przykład separacji, której szukasz?