Problem nierozstrzygalny

Problem nierozstrzygalny – problem decyzyjny, dla którego nie istnieje algorytm, który po skończonej liczbie kroków i dla dowolnych danych wejściowych jednoznacznie odpowie tak lub nie[1].

Turing w 1936 roku wykazał, że udzielenie odpowiedzi na pytanie, czy maszyna Turinga o numerze n , {\displaystyle n,} wykonując działania nad liczbą m , {\displaystyle m,} zakończy kiedyś swoją pracę, czy też przewidziany dla niej algorytm będzie realizowany w nieskończoność, jest problemem nierozstrzygalnym (patrz: problem stopu)[1][2].

Innym przykładem problemu nierozstrzygalnego jest tzw. zdanie Gödla o postaci 17 Gen r (generalizacja {kwantyfikator ogólny} formuły r względem zmiennej z numerem 17). Jest to zdanie posiadające tę własność, że ani ono, ani jego negacja nie dają się formalnie dowieść. Zdanie nierozstrzygalne 17 gen r powstało w wyniku odwzorowania antynomii logicznej (zwanej antynomią Richarda)[3] poprzez tak zwaną arytmetyzacją języka klasycznego rachunku zdań. Arytmetyzacja języka pozwala na odwzorowanie relacji logicznych jakie zachodzą między zdaniami w relacje arytmetyczne między liczbami stanowiącymi numery tych zdań. Dzięki temu zamiast o relacjach logicznych można mówić o relacjach arytmetycznych[4].

Istnienie zdania 17 gen r jest powodem nierozstrzygalności arytmetyki, uważanej do czasów Gödla za system rozstrzygalny, to znaczy taki, w którym prawdziwość każdego twierdzenia można rozstrzygnąć w oparciu o skończony zbiór kryteriów. Inaczej mówiąc, zbiór twierdzeń arytmetycznych jest nieobliczalny, co znaczy, że nie można w skończonej ilości kroków rozstrzygnąć, czy dany element tego zbioru, będący twierdzeniem arytmetycznym, jest, czy nie jest elementem zbioru twierdzeń. Tymczasem zbiór dowodów systemu formalnego jest obliczalny, ponieważ w skończonej ilości kroków można rozstrzygnąć, czy dany ciąg napisów jest, czy nie jest dowodem danego twierdzenia.

Tak więc zbiór zdań prawdziwych nie pokrywa się ze zbiorem twierdzeń dowodzonych przez system. Wiemy bowiem, że istnieją zdania prawdziwe, których nie da się dowieść w tym systemie. Jednym z nich jest właśnie zdanie 17 Gen r.

Przykłady problemów nierozstrzygalnych

Nierozstrzygalność problemu stopu

 Osobny artykuł: Problem stopu.

Nie istnieje maszyna Turinga rozstrzygająca w skończonej liczbie kroków, czy dowolna maszyna Turinga zakończy pracę.

Nierozstrzygalność Entscheidungsproblem

 Osobny artykuł: Dowód Turinga.

Nie istnieje algorytm rozstrzygający w skończonej liczbie kroków, czy dana formuła jest dowodliwa w wybranym systemie aksjomatycznym[5].

Nierozstrzygalność pytania o istnienie rozwiązania równania diofantycznego

 Osobny artykuł: Dziesiąty problem Hilberta.

Równanie diofantyczne jest równaniem postaci:

D ( x 1 , … , x m ) = 0 , {\displaystyle D(x_{1},\dots ,x_{m})=0,}

gdzie D {\displaystyle D} jest wielomianem o współczynnikach całkowitych. Współczynniki wielomianu D można jednoznacznie zakodować w postaci odpowiedniego, skończonego ciągu liczb całkowitych.

Nie istnieje maszyna Turinga rozstrzygająca w skończonej liczbie kroków, czy dane równanie diofantyczne ma rozwiązanie w dziedzinie liczb całkowitych[6].

Nierozstrzygalność problemu równoważności dla rachunku lambda

Wyobraźmy sobie, że istnieje algorytm w postaci λ-wyrażenia E {\displaystyle E} rozstrzygający, czy dwa λ-wyrażenia są równoważne: algorytm bierze cztery wyrażenia, po czym zwraca trzecie, jeśli dwa pierwsze są równoważne lub czwarte w przeciwnym wypadku.

Y ( λ f . E f t r u e f a l s e t r u e ) {\displaystyle Y(\lambda f.Ef\,\mathrm {true\,false\,true} )}

Jeśli E {\displaystyle E} zwróci true, wyrażenie zwróci false, jeśli E {\displaystyle E} zwróci false, wyrażenie zwróci true.

Nierozstrzygalność problemu słowa dla półgrup

Problemem jest rozstrzygnięcie, czy x = y {\displaystyle x=y} ( x , y ∈ A , G = ⟨ A , ⊙ ⟩ ) {\displaystyle (x,y\in A,G=\langle A,\odot \rangle )} dla dowolnej struktury spełniającej skończony zbiór równoważności E {\displaystyle E} [7]. Naturalną reprezentacją półgrup są ciągi elementów nad skończonym alfabetem z działaniem konkatenacji, stąd nazwa problemu.

Nierozstrzygalność problemu pokrycia płaszczyzny

Można pokazać, że powyższy zbiór 11 płytek pozwala na pokrycie płaszczyzny, jednak tylko w sposób nieokresowy.

Przypuśćmy, że dysponujemy skończonym zbiorem jednostkowych kwadratów ze zdefiniowanymi kolorami krawędzi poziomych i pionowych. Przedmiotem problemu jest pytanie, czy możliwe jest pokrycie płaszczyzny euklidesowej elementami tego zbioru, stosując jedynie translacje (bez obrotów) przy założeniu, że sąsiadujące krawędzie dowolnej pary kwadratów muszą mieć ten sam kolor. Nie istnieje ogólny algorytm odpowiadający na tak postawione pytanie w skończonej liczbie kroków[8].

Jeżeli dla danego zbioru płytek pokrycie nie istnieje lub istnieje pokrycie okresowe (symetryczne względem pewnej niezerowej translacji), to odpowiedź na wyżej postawione pytanie zawsze można uzyskać w skończonej liczbie kroków, po prostu pokazując wystarczająco szeroki obszar płaszczyzny, którego nie da się pokryć lub (w przypadku pokrycia okresowego), który można pokryć w całości.

Można również podać pewne kryteria, pozwalające dowieść w niektórych przypadkach, że istnieje pokrycie nieokresowe (jak w przypadku pokazanym na obrazku po prawej), jednak żaden skończony zbiór kryteriów nie wystarcza do uwzględnienia wszystkich przypadków zbiorów kwadratów, dla których istnieje jedynie pokrycie nieokresowe.

Nierozstrzygalność uogólnionego problemu Collatza

Funkcją g ( n ) {\displaystyle g(n)} nazywamy takie przekształcenie w dziedzinie liczb całkowitych, które jest określone przez pewien skończony ciąg par liczb rzeczywistych ( a 0 , b 0 ) , ( a 1 , b 1 ) , … , ( a P − 1 , b P − 1 ) {\displaystyle (a_{0},b_{0}),(a_{1},b_{1}),\dots ,(a_{P-1},b_{P-1})} w następujący sposób:

g ( n ) = a i n + b i , {\displaystyle g(n)=a_{i}n+b_{i},} gdzie i = n mod P {\displaystyle i=n{\bmod {P}}}

i które ma tę własność, że jego zbiór wartości zawiera się w zbiorze liczb całkowitych.

Przedmiotem problemu jest pytanie, czy dla każdej dodatniej liczby naturalnej istnieje takie wielokrotne złożenie funkcji g ( n ) , {\displaystyle g(n),} że jego wartość dla tej liczby to 1. Można pokazać, że problem ten jest nierozstrzygalny[9], to znaczy, nie istnieje ogólny algorytm, który działając na dowolny ciąg par określających funkcje g ( n ) , {\displaystyle g(n),} odpowiada na tak postawione pytanie poprawnie. Można zauważyć, że problem Collatza to przypadek, gdy ciąg par to { ( a 0 = 0 , 5 , b 0 = 0 ) , ( a 1 = 3 , b 1 = 1 ) {\displaystyle (a_{0}=0{,}5,b_{0}=0),(a_{1}=3,b_{1}=1)} }, P = 2. {\displaystyle P=2.}

Zobacz też

Przypisy

  1. ↑ a b Lewis i Papadimitriou 1998 ↓, s. 254.
  2. ↑ Lewis i Papadimitriou 1998 ↓, s. 273.
  3. ↑ Nagel i Newman 1958 ↓, s. 46.
  4. ↑ Nagel i Newman 1958 ↓, s. 60.
  5. ↑ Alan Turing. On Computable Numbers, With an Application to the Entscheidungsproblem. „Proceedings of the London Mathematical Society”. 42 (1), s. 231, 1937. DOI: 10.1112/plms/s2-42.1.230. 
  6. ↑ YuriY. Matiyasevich YuriY., MartinM. Davis MartinM., HilaryH. Putnam HilaryH., Hilbert’s 10th Problem (Foundations of Computing), The MIT Press, 1993, s. 93, ISBN 978-0262132954 .
  7. ↑ Yuri Gurevich, Harry L. Lewis, The Word Problem for Cancellation Semigroups with Zero, s. 184.
  8. ↑ Raphel M. Robinson. Undecidability and nonperiodicity for tilings of the plane. „Inventiones Mathematicae”. 12 (1–3), s. 177–209, 1971. DOI: 10.1007/bf01418780. 
  9. ↑ John H.J.H. Conway John H.J.H., Unpredictable Iterations, [w:] Proc. 1972 Number Theory Conf., Boulder: Univ. Colorado, 1972, s. 49–52 .

Bibliografia

  • Harry Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1998. ISBN 978-0-13-262478-7.
  • Ernest Nagel, James R. Newman: Gödel’s Proof. London: Routledge and Kegan Paul, 1958. ISBN 0-415-35528-1.