Kompletność Turinga opisuje zdolność systemu polegającą na możliwości rozwiązywania identycznej klasy problemów, jak na uproszczonym modelu programowalnego komputera – maszyny Turinga. Inaczej mówiąc, jest to zdolność systemu obliczeniowego do symulacji innego systemu obliczeniowego pod warunkiem dostarczenia takich zasobów jak czas i pamięć. W dzisiejszym artykule chcielibyśmy opowiedzieć Wam o postaci Alana Turinga oraz jego wkładzie w naukę. 

Alan Turing – wybitny matematyk i logik

Postać Alana Turinga zapisała się w historii jako jeden z ojców współczesnej informatyki. Urodził się on 23 czerwca 1912 roku. Od dziecka wykazywał on wyjątkowe zdolności matematyczne. Zdobył wykształcenie na Uniwersytecie w Cambridge, gdzie jego praca doprowadziła do stworzenia koncepcji maszyny Turinga – takiej, która byłaby w stanie wykonywać dowolne obliczenia, jeśli byłyby one algorytmicznie możliwe do wykonania. W trakcie II wojny światowej pracował nad złamaniem Enigmy. Był także pionierem sztucznej inteligencji, tworząc test Turinga pozwalający stwierdzić, czy maszyna myśli w sposób podobny do ludzkiego. Zmarł w wieku zaledwie 41 lat, 7 czerwca 1954 roku. 

Ciekawostka: Odwróconą formą testu Turinga jest CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) pozwalająca stwierdzić czy program wchodzi w interakcję z człowiekiem, czy np. botem sztucznej inteligencji. 

Maszyna Turinga – działanie 

W 1936 roku matematyk zaproponował abstrakcyjny model obliczeniowy definiujący teoretyczne podstawy działania współczesnych komputerów. Maszyna Turinga składa się z następujących elementów: nieskończonej taśmy podzielonej na komórki, głowicy mogącej odczytywać i zapisywać symbole na taśmie oraz zestawu reguł sterujących głowicą. Model pozwala na wykonywanie dowolnych obliczeń jeśli są one algorytmicznie możliwe do wykonania i jest w stanie symulować działanie każdego innego komputera.

Kompletność Turinga – definicja

Opisana wyżej maszyna Turinga jest podstawą do zdefiniowania kompletności Turinga, która jest zdolnością systemu obliczeniowego do wykonywania obliczeń, które są teoretycznie możliwe do wykonania przez maszynę. Jak wspomniano we wstępie – jeśli dany język programowania lub system obliczeniowy jest kompletny w sensie Turinga, wówczas może on symulować każdy inny system obliczeniowy, zakładając, że ma wystarczająco pamięci i czasu. 

Podsumowanie – co łączy kryptowaluty i kompletność Turinga? 

O Maszynie Wirtualnej Ethereum (EVM) mówi się, iż cechuje ją kompletność Turinga. Operacje w ramach sieci Ethereum wymagają użycia gazu (gas) do realizacji postanowień zawartych w smart kontraktach. Gaz to jednostka miary zasobów obliczeniowych potrzebnych do realizacji danego zadania. Dzięki jego istnieniu nie może dojść do zapętlenia sieci. Zapewnia on także wynagrodzenie dla walidatorów. Ethereum cechuje kompletność Turinga, ponieważ dzięki temu, iż EVM umożliwia wykonywanie dowolnych obliczeń, jeśli zostaną zapewnione odpowiednie zasoby. 

Naturalnie, Ethereum nie jest odosobnionym przypadkiem kompletności Turinga w sieci blockchain. Jest wiele innych prominentnych przykładów, takich jak np. Cardano, TRON, NEO, Tezos, Polkadot, Solana i wiele innych, które również zapewniają użytkownikom różnorodne korzyści i rozwiązania, jednocześnie cechując się kompletnością Turinga.