Można pokazać — i to był pierwotny argument Turinga — że istnieją pro­blemy, których żadna maszyna Turinga nigdy nie bę­dzie w stanie rozwiązać; może ona bez końca przesu­wać swą taśmę, nie dochodząc do rozwiązania. Takie problemy ukazują ostateczne, choć nie jedyne, ograni­czenie mocy komputera cyfrowego.Prześledziliśmy logiczny duch komputera w maszynie Turinga. Aczkolwiek pomysłowe, urządzenie to […]

Maszyna Turinga nie pracuje, jak czyni to maszyna parowa, a jedynie tam i z powrotem przesuwa swój znacznik wzdłuż taś­my, analizując, ścierając i wpisując symbole stosow­nie do swych reguł działania. Taka maszyna nie zwięk­sza zdolności fizycznego panowania człowieka nad przyrodą, zatem słowa „maszyna” powinniśmy używać tylko per analogiam. Bez względu na nazwę, abstrak­cja Turinga faktycznie […]

Okazuje się, że logik nie musi konstruować nowej maszyny, zawierającej nowe re­guły, dla każdego zadania programistycznego. Można zaprojektować jedną maszynę, uniwersalną maszynę Turinga, w ten sposób, iż mając dane właściwe sym­bole wejściowe na taśmie, potrafi ona wykonywać wszelkie zadania, które może wykonać każda poje­dyncza maszyna Turinga. Za taką uniwersalną maszy­nę Turinga może być uznany komputer […]

Ta komórka jest pusta, a maszyna znajduje się w sta­nie Q2, zatem obowiązuje reguła numer dwa. Maszyna wpisuje „0”, przesuwa swój znacznik na prawo i za­trzymuje się. Program się skończył, jego skromnym wynikiem jest zastąpienie liczby 1 przez liczbę 10.Oczywiście, istnieje nieograniczona liczba innych, bardziej interesujących maszyn Turinga. Ich zasady działania są takie same, niezależnie […]

Są to jedyne środki, za po­mocą których maszyna Turinga może operować dany­mi. Proces ten powtarza się w ten sam sposób tak długo, póki maszyna nie napotka reguły, która naka­zuje jej zatrzymać się; wówczas maszyna ukończyła swoje zadanie.Maszyna Turinga jest grą, w której nie ma miejsca na inicjatywę gracza. Jedyny element, który może się zmieniać, to […]

Powia­da się, że przed i po każdym wykonanym działaniu maszyna znajduje się w jednym z ograniczonej liczby stanów. Są one zdefiniowane przez logika, który skon­struował maszynę; w naszym przykładzie nazwane zo­stały Q1 i Q2. Maszyna zawsze „wie” dwie rzeczy: zna swój aktualny stan oraz aktualną komórkę taśmy wskazywaną przez znacznik. Te dwa czynniki to wszy­stko, […]