Maszyna Turinga

Z encyklopediafantastyki.pl
Skocz do: nawigacji, wyszukiwania
LEKSYKON FANTASTYKI
science


Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej "głowicy", wykonującej proste operacje na zapisanych na taśmie wartościach.

Artystyczna wizja Maszyny Turinga. Źródło: Internet

Ten abstrakcyjny model komputera służącego do wykonywania algorytmów, składającego się z nieskończenie długiej taśmy podzielonej na pola stworzony został przez Alana Turinga. Przebywając od 1931 roku w Cambridge Turing napisał swoją prawdopodobnie najważniejszą pracę matematyczną On Computable Numbers. W niej wprowadził abstrakcyjną maszynę, która była w stanie wykonywać zaprogramowaną matematyczną operację, czyli tak zwany algorytm. Maszyna mogła wykonać tylko jeden, określony algorytm, na przykład mogła podnieść liczbę do kwadratu, podzielić, dodać, odjąć. Według Turinga liczby miały być podawane maszynie za pomocą papierowej taśmy podobnej do taśmy z melodią zapisaną dla pianoli. W swojej pracy Turing opisał wiele takich maszyn, które uzyskały wspólne miano maszyn Turinga. Następnie Turing opracował tak zwaną uniwersalną maszynę Turinga, która w zależności od instrukcji zapisanej na taśmie, miała wykonywać dowolną operację. W tej samej pracy Turing przedstawił schemat pierwszego komputera przygotowany w oparciu o prace Charlesa Babbage'a i jego projekt maszyny różnicowej nr 2.

W informatyce dowodzi się równoważności wielu różnych wariantów maszyny Turinga. Mimo że maszyna Turinga jest abstrakcją o dużej mocy obliczeniowej (większej na przykład niż dowolny komputer), istnieje wiele problemów, których nie da się na niej rozwiązać. Matematycy rozważają więc (od czasów samego Turinga) modele obliczeń, które mogą takim zadaniom podołać. Hipotetyczne maszyny potrafiące wykonywać takie obliczenia, nazywa się hiperkomputerami.

Zobacz też:

Osobiste
Przestrzenie nazw
Warianty
Działania
Nawigacja
Narzędzia
Pomoc
Szablony