Niedeterministyczna maszyna Turinga a liczby pierwsze

lasek0110

Nowicjusz
Dołączył
22 Październik 2009
Posty
166
Punkty reakcji
4
Wiek
29
Miasto
Polska
Witam!
Drobne wprowadzenie, o maszynie Turinga. Otóż jest to model hipotetycznego komputera, składającego się z taśmy o nieskończonej długości podzielonej na pola, oraz z głowicy. Pole może mieć jeden z n stanów, a głowica jeden z m stanów. Głowica po otrzymaniu polecenia od programu sterującego może zmienić wartość pola nad którym się znajduje, zmienić swój stan a następnie przesunąć się w lewo, w prawo lub zakończyć pracę. Takie urządzenie służy do wykonywania algorytmów. Dla zainteresowanych odsyłam do szczegółowego artykułu na Wikipedii: http://pl.wikipedia.org/wiki/Maszyna_Turinga (przepraszam tych, którzy już wiedzą, o czym mowa).

Z tego, co dowiedziałem się na wykładzie wynika, że niedeterministyczna maszyna Turinga może składać się z N taśm, a dla danej pary pole-stan może istnieć więcej niż jedna instrukcja. Zatem problemy o złożoności obliczeniowej i czasowej klasy NP można by przesunąć do klasy P.

Generowanie (a w zasadzie sprawdzanie, czy zadana liczba jest liczbą pierwszą) jest problemem o złożoności obliczeniowej O(n^2) (o ile dobrze pamiętam, jeśli się mylę, przepraszam za błąd). Czy zatem budowa fizycznej niedeterministycznej maszyny Turinga pozwoliłaby na odkrycie algorytmu generowania liczb pierwszych, o wielomianowej złożoności? Czy spowodowałoby to upublicznienie wszystkich tajnych danych, skoro podstawa współczesnej kryptografii stoi właśnie na liczbach pierwszych?\

Pozdrawiam!
 
N

Naxxramas

Guest
lasek0110 napisał:
Czy zatem budowa fizycznej niedeterministycznej maszyny Turinga pozwoliłaby na odkrycie algorytmu generowania liczb pierwszych, o wielomianowej złożoności?
Chyba nie trzeba maszyny Alana do tego algorytmu, poza tym nie można w materii barionowej zbudować czegoś co ma niekończące się taśmy.




lasek0110 napisał:
Czy spowodowałoby to upublicznienie wszystkich tajnych danych, skoro podstawa współczesnej kryptografii stoi właśnie na liczbach pierwszych?\
Liczby pierwsze nie są jedynym składnikiem algorytmu. Są przecież tablice znanych liczb pierwszych więc gdyby to było takie proste każdy ma je już podane na talerzu bez liczenia.

Co do algorytmu na razie znamy prostu i wolny - sprawdzasz ile dzielnych ma liczba. Na satysfakcjonujące wyniki trzeba będzie poczekać do komputerów kwantowych.




MNICH OŚWIECONY
 
Do góry