Problemy trudnorozwiązywalne 3

Nierozstrzygalny jest tez problem weryfikacji algorytmów. Już wcześniej mówiliśmy, że nie istnieje automatyczny (algorytmiczny) weryfikator poprawności programów (algorytmów). Co więcej, nie jesteśmy nawet w stanie stwierdzić dla wszystkich algorytmów czy dany algorytm sie zatrzyma dla wszystkich poprawnych danych wejściowych, a nawet, że uczyni to choćby dla pewnych wybranych danych.

Problem STOPU jest nierozstrzygalny, a dowód tego faktu jest w książce Horela. Na domiar złego takie problemy nierozstrzygalne mają różne stopnie nierozstrzygalności. całą hierarchię, a wśród nich są problemy wysoce nierozstrzygalne.

Cztery poziomy algorytmicznego zachowania sie Można wyróżnić cztery takie typy:

ni eo graniczone domino

ograniczone domino (przypuszczalnie)

okresowe

domino

ograniczone domino ze stała szeroko śaą (ma algorytm wielomianowy)

Nie byłoby w tym nic specjalnie ciekawego, gdyby nie fakt, że ten sam problem przy pewnych specyficznych sformułowaniach może należeć do każdej z tych klas. Weźmy problem domina:

Domino ograniczone

problem pokrycia kwadratu N x N dla danego N za pomocą skończonego zbioru rodzajóyy kafelków T (nieskończenie wiele kafelków danego typu, reguła — krawędzie o jednakowych kolorach, muszą się stykać),

Domino nieograniczone

problem pokrycia nieskończonej siatki liczb naturalnych za pomocą skończonego zbioru T,

Domino okresowe

tak jak poprzednio, ale żądamy by pewien określony kafelek powtórzył się w pokryciu nieskończenie wiele razy,

Domino o stałej szerokości

czy dla danego T i liczby N można ze zbioru T ustawić prostokąt o wymiarach C x N (C — szerokość z góry ustalona zgodnie z regułami domina. Np. dla C = 1 będzie to linia kafelków ustawiona zgodnie z regułami.

Na koniec ostatnia pesymistyczna uwaga — nawet problemy trudnorozwiazywalne. a więc jeszcze nie najgorsze mogą nie mieć praktycznie akceptowalnych rozwiązań!!:(