Maszyna Turinga: Różnice pomiędzy wersjami

Usunięte 2 bajty ,  4 lata temu
m
→‎Wstęp: ilość a liczba
m (-przykłady (są i tak bez źródeł, a słabo sformatowane i abstrakcyjne, a także bez omówienia))
m (→‎Wstęp: ilość a liczba)
Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w [[rachunek lambda|rachunku lambda]] i odwrotnie. Ponieważ jednak maszyny Turinga rozszerza się bardzo trudno, zaś rachunek lambda bardzo łatwo, w praktyce są one o wiele mniej popularne jako rzeczywiste modele obliczeń. Są za to używane często do udowadniania nierozstrzygalności różnych problemów.
 
Maszyna Turinga A posiadająca zdolność symulacji działania dowolnej innej maszyny Turinga B (opisanej jako dane wejściowe dla maszyny A) na dowolnych danych wejściowych dla maszyny B, nazywana jest uniwersalną maszyną Turinga. Praktycznym przybliżeniem realizacji uniwersalnej Maszyny Turinga jest [[komputer]], będący w stanie wykonać dowolny [[program komputerowy|program]] na dowolnych danych. Jednak komputery nie są uniwersalnymi maszynami Turinga w sensie pierwotnej definicji, ponieważ ilość danych, które mogą przechowywać i przetwarzać jest skończona, tak więc dla każdego komputera istnieje tylko skończona ilośćliczba programów, które może wykonać. Mimo że ilośćliczba ta jest niewyobrażalnie wielka i w praktyce często wystarczająca, to bez względu na rozmiar pamięci, zawsze będzie istnieć program, którego maszyna nie będzie w stanie wykonać, ponieważ jego kod (opis) po prostu nie mieści się w tej pamięci.
 
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.
50

edycji