Rozstrzygalność

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: istnieje algorytm, który oblicza odpowiedź na dowolne pytanie stawiane przez problem.

Problem może być nierozstrzygalny, jeśli jego rozstrzygalność prowadziłaby do powstania sprzeczności.

Przykłady z dziedziny informatyki[edytuj]

Nierozstrzygalność problemu stopu[edytuj]

 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[edytuj]

 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. [1]

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

 Osobny artykuł: Dziesiąty problem Hilberta.

Równanie diofantyczne jest równaniem postaci:

gdzie 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 Turina rozstrzygająca w skończonej liczbie kroków czy dane równanie diofantyczne ma rozwiązanie w dziedzinie liczb całkowitych. [2]

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

Wyobraźmy sobie, że istnieje algorytm w postaci λ-wyrażenia 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.

Jeśli zwróci true, wyrażenie zwróci false, jeśli zwróci false, wyrażenie zwróci true.

Nierozstrzygalność uogólnionego problemu Collatza[edytuj]

Funkcją nazywamy takie przekształcenie w dziedzinie liczb całkowitych, które jest określone przez pewien skończony ciąg par liczb rzeczywistych w następujący sposób:

, gdzie i = n mod 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 że jego wartość dla tej liczby to 1. Można pokazać że ten problem jest nierozstrzygalny[3] to znaczy nie istnieje ogólny algorytm, który działając na dowolny ciąg par określających funkcje odpowiada na tak postawione pytanie poprawnie. Nietrudno zaważyć, że problem Collatza to przypadek gdy ciąg par to {}, .

Przypisy

  1. 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. 
  2. Hilbert's 10th Problem (Foundations of Computing), The MIT Press, 1993, s. 93, ISBN 978-0262132954.
  3. Conway, John H. (1972), "Unpredictable Iterations", Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder str. 49–52, 1972, s. 49–52.