Rozstrzygalność

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

Nierozstrzygalność problemu stopu

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

Nierozstrzygalność Entscheidungsproblem

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

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

Równanie diofantyczne jest równaniem postaci:

$D(x_{1},...,x_{m})=0$

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.

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

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.

$Y(\lambda f.Ef\,\mathrm {true} \,\mathrm {false} \,\mathrm {true} )$

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

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

Problemem jest rozstrzygnięcie czy $x=y$ $(x,y\in A,G=\langle A,\odot \rangle )$ dla dowolnej struktury spełniającej skończony zbiór równoważności $E$ . 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

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.

Nierozstrzygalność uogólnionego problemu Collatza

Funkcją $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})$ w następujący sposób:

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