Teza Churcha Turinga 2

Maszyna Turinga a problem czy P = NP

W oparciu o MT można na nowo zdefiniować klasy P i NP.

Klasa NP

problemy rozwiązywalne w czasie wielomianowym przez niedeterministyczna maszynę Turinga Klasa P

problemy rozwiązywalne w czasie wielomianowym przez zwykłe (deterministyczne, sekwencyjne) MT; (sekwencyjne oznacza tu sprawdzające po kolei wszystkie drogi, nie "odgadujące" właściwej).

Gdyby niedeterministyczne MT spełniały kryterium sekyyencyjności. to z tezy CT wynikałoby P = NP. Ale maszyny T niedeterministyczne nie są sekwencyjne, bo stosuje się tu "magię", bez tego musiałyby wszystkie możliwości sprawdzać równocześnie. Sprawdzanie po kolei czyli sekwencyjność wymagałoby czasu wykładniczego.

Zatem MT nie pomoże nam w rozstrzygnięciu czy P = NP czy # NP.

Czy przy pomocy MT da się udowodnić tezę odwrotną, że P * NP?

Trzeba pokazać, że MT nie może rozwiązać pewnego problemu klasy NPC w czasie krótszym niż wykładniczy, jeśli nie da się na żadnej MT rozwiązać małpiej układanki w czasie lepszym niż wykładniczy, to znaczy że jest problem istotnie trudnorozwiązywalny, bo na mocy CT nie da się go w czasie wielomianowym rozwiązać na żadnej maszynie sekwencyjnej. A jeśli jest on istotnie trudnorozwiązywalny, to z definicji takie są wszystkie problemy klasy NPC czyli P # NP. Ale najpierw trzeba udoyyodnić że małpiej układanki nie da sie rozwiązać na żadnej maszynie Turinga. Maszyny T często stosuje się do dowodzenia ograniczeń dolnych wykorzystując oczywiście warianty tezy CT.

Problem uniwersalnej maszyny Turinga:

Jak widać z naszych przykładów, dla każdego z nich konstruowaliśmy odpowiednią maszynę Turinga dobierając liczbę znaków alfabetu i liczbę stanów. (Czymś inny jest dobór listy rozkazów, bo to oprogramowanie, nie sprzęt). Czy można znaleźć uniwersalną MT zdolną wykonać dowolny algorytm czyli znaleźć taki odpowiedni wybór alfabetu i stanów dobry dla każdego algorytmu? TAK. Ale taką rzeczywistą konstrukcję znalazł dopiero Shannon. Dziś badaczy interesuje pojęcie minimalnej uniwersalnej MT. czyli konstrukcji o najmniejszym iloczynie liczby stanów automatu Q i liczby symboli alfabetu 2. Najlepszy wynik na dziś podał A. Tritter i wynosi on 4 symbole alfabetu x 6 stanów = 24