Poszukiwali oni sposobów zbudowania maszyn Turin­ga z próżniowych lamp elektronicznych zamiast kon­strukcji na papierze. Elektroniczna wersja pracowała­by miliony razy szybciej niż matematyk stosujący te reguły i stosownie do nich piszący symbole.Trzeba było rozważyć dwie sprawy: reguły działania oraz dane, do których mają one być zastosowane. Dane mogły być zaznaczone na kartach dziurkowanych, we­wnątrz maszyny’przedstawione przez […]

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 […]