Maszyna Turinga: Różnice pomiędzy wersjami

Dodane 24 bajty ,  4 lata temu
poprawa linku
(zobacz też)
(poprawa linku)
Można rozważać bardzo wiele różnych wariantów maszyny Turinga. Na przykład nie ma potrzeby pozwalać na pozostanie maszyny na tym samym polu, ponieważ maszyna musi albo zakończyć obliczenia przez zapętlenie, albo po nie więcej niż N*M krokach dane pole opuścić i wystarczy wtedy przyjąć dla danej kombinacji początkowej stany podczas opuszczania pola.
 
Istnieją też maszyny Turinga wielotaśmowe lub [[determinizmNiedeterministyczna maszyna Turinga|niedeterministyczne]] (gdzie jednej parze (symbol, stan) może odpowiadać kilka instrukcji) oraz wielowymiarowe (prostą dwuwymiarową maszyną Turinga jest [[mrówka Langtona]]).
 
W informatyce dowodzi się równoważności wielu różnych wariantów maszyny Turinga. Np. dość łatwo jest pokazać, że maszyna Turinga z wieloma taśmami nie różni się istotnie od klasycznej maszyny jednotaśmowej. Również niedeterministyczne maszyny Turinga są równoważne deterministycznym. Rozważania na temat mocy obliczeniowej niedeterministycznych maszyn Turinga są podstawą centralnego problemu [[Złożoność obliczeniowa|teorii złożoności obliczeniowej]] – „P versus NP”.