Prawdopodobieństwo uniwersalności

Prawdopodobieństwo uniwersalności jest zawiłą miarą prawdopodobieństwa w teorii złożoności obliczeniowej , która dotyczy uniwersalnych maszyn Turinga .

Tło

Maszyna Turinga jest podstawowym modelem obliczeń . Niektóre maszyny Turinga mogą być specyficzne dla wykonywania określonych obliczeń. Na przykład maszyna Turinga może pobierać dane wejściowe składające się z dwóch liczb, a następnie generować dane wyjściowe będące iloczynem ich mnożenia . Inna maszyna Turinga może pobierać dane wejściowe, które są listą liczb, a następnie dawać dane wyjściowe, które są posortowanymi liczbami .

Maszyna Turinga , która może symulować dowolną inną maszynę Turinga, nazywana jest uniwersalną — innymi słowy, o maszynie Turinga (TM) mówi się, że jest uniwersalną maszyną Turinga (lub UTM), jeśli dla dowolnej innej TM istnieje pewna wejście (lub „nagłówek”) w taki sposób, że pierwsza TM mająca ten wejściowy „nagłówek” będzie się zachowywać jak druga TM.

interesujące pytanie matematyczne i filozoficzne . Jeśli uniwersalna maszyna Turinga otrzyma losowe dane wejściowe (dla odpowiedniej definicji losowości ), jakie jest prawdopodobieństwo, że pozostanie ona uniwersalna na zawsze?

Definicja

Biorąc pod uwagę maszynę Turinga bez przedrostków , jej prawdopodobieństwo uniwersalności jest prawdopodobieństwem , że pozostanie ona uniwersalna , nawet jeśli każde jej wejście (jako ciąg binarny ) jest poprzedzone losowym ciągiem binarnym. Bardziej formalnie jest to miara prawdopodobieństwa liczb rzeczywistych (nieskończonych ciągów binarnych), które mają tę właściwość, że każdy ich początkowy segment zachowuje uniwersalność danej maszyny Turinga. Pojęcie to zostało wprowadzone przez informatyka Chrisa Wallace'a i został po raz pierwszy wyraźnie omówiony w druku w artykule Dowe'a (i kolejnym artykule). Jednak odpowiednie dyskusje pojawiają się również we wcześniejszym artykule Wallace'a i Dowe'a.

Prawdopodobieństwa uniwersalności UTM bez przedrostków są niezerowe

Chociaż pierwotnie podejrzewano, że prawdopodobieństwo uniwersalności UTM ( UTM) wynosi zero, istnieją stosunkowo proste dowody na to, że supremum zbioru prawdopodobieństw uniwersalności jest równe 1, takie jak dowód oparty na spacerach losowych i dowód w Barmpalias i Dowe (2012). Gdy ktoś ma jeden bez prefiksów z niezerowym prawdopodobieństwem uniwersalności, natychmiast wynika z tego, że wszystkie UTM bez prefiksów mają niezerowe prawdopodobieństwo uniwersalności. Dalej, ponieważ supremum zbioru prawdopodobieństw uniwersalności wynosi 1 i ponieważ zbiór { m / 2 n | 0 < n & 0 < m < 2 n } jest gęsty w przedziale [0, 1], odpowiednie konstrukcje UTM (np. jeśli U jest UTM, zdefiniuj UTM U 2 przez U 2 (0 s ) zatrzymuje się dla wszystkich struny s , U 2 (1 s ) = U ( s ) dla wszystkich s) daje, że zbiór prawdopodobieństw uniwersalności jest gęsty w przedziale otwartym (0, 1).

Charakterystyka i losowość prawdopodobieństwa uniwersalności

Prawdopodobieństwo uniwersalności zostało dokładnie zbadane i scharakteryzowane przez Barmpaliasa i Dowe'a w 2012 roku. Postrzegane jako liczby rzeczywiste , te prawdopodobieństwa zostały całkowicie scharakteryzowane pod względem pojęć z teorii obliczalności i algorytmicznej teorii informacji . Wykazano, że gdy maszyna bazowa jest uniwersalna, liczby te są wysoce algorytmicznie losowe . Mówiąc dokładniej, jest to Martina-Löfa względem trzeciej iteracji problemu zatrzymania . Innymi słowy, są losowe względem zbiorów zerowych, które można zdefiniować za pomocą czterech kwantyfikatorów w arytmetyce Peano . I odwrotnie, przy tak wysoce losowej liczbie [ wymagane wyjaśnienie ] (z odpowiednimi właściwościami aproksymacyjnymi) istnieje maszyna Turinga z prawdopodobieństwem uniwersalności tej liczby.

Związek ze stałą Chaitina

Prawdopodobieństwa uniwersalności są bardzo związane ze stałą Chaitina , która jest prawdopodobieństwem zatrzymania uniwersalnej maszyny bez przedrostków. W pewnym sensie są one komplementarne do prawdopodobieństw zatrzymania maszyn uniwersalnych względem trzeciej iteracji problemu zatrzymania . W szczególności prawdopodobieństwo uniwersalności można postrzegać jako prawdopodobieństwo braku zatrzymania maszyny z wyrocznią trzeciej iteracji problemu zatrzymania. I odwrotnie, prawdopodobieństwo niezatrzymania dowolnej maszyny bez przedrostków z tą wysoce nieobliczalną wyrocznią jest prawdopodobieństwem uniwersalności jakiejś maszyny bez przedrostków.

Prawdopodobieństwa maszyn jako przykłady liczb wysoce losowych

Prawdopodobieństwo uniwersalności stanowi konkretny i nieco naturalny przykład wysoce losowej liczby (w sensie algorytmicznej teorii informacji ). W tym samym sensie stała Chaitina stanowi konkretny przykład liczby losowej (ale dla znacznie słabszego pojęcia losowości algorytmicznej).

Zobacz też

Linki zewnętrzne

Dalsza lektura

  • Ming Li i Paul Vitányi (1997). Wprowadzenie do złożoności Kołmogorowa i jej zastosowań . Skoczek. Rozdział wprowadzający pełny tekst .
  •   Cristian S. Calude (2002). Informacje i losowość: perspektywa algorytmiczna , wydanie drugie. Skoczek. ISBN3-540-43466-6 _
  • R. Downey i D. Hirschfeldt (2010), Algorytmiczna losowość i złożoność , Springer-Verlag.
Pobrano z „ https://en.wikipedia.org/w/index.php?title=Universality_probability&oldid=1122129221 ”