Turing komplett

Turing Complete hänvisar till en maskin som, med tillräckligt med tid och minne tillsammans med nödvändiga instruktioner, kan lösa alla beräkningsproblem, oavsett hur komplexa de är. Termen används normalt för att beskriva moderna programmeringsspråk eftersom de flesta av dem är Turing Complete (C++, Python, JavaScript, etc.).

Vad är en Turing-maskin?

Före dagens datorer antog Alan Turing att det en dag skulle finnas en maskin som kunde lösa alla problem. Denna maskin blev känd som Turing Machine.

Alan föreställde sig sin maskin som ett långt band med information skriven på den i form av binär kod (1:or och 0:or). Maskinen skulle också ha ett läs-/skrivhuvud som rör sig längs bandet och läser varje ruta, en efter en. Koden skulle fråga maskinen om ett beräkningsproblem, och bandet skulle vara så långt som behövdes för att uppnå en lösning.

När huvudet rör sig längs tejpen följer maskinen enkla instruktioner som styr hur den reagerar. Den läser bandet, följer instruktionerna och utför en viss åtgärd för att skriva en ny kod när den rör sig. Detta nya kodmönster är svaret på problemet. Turings hypotetiska maskin kunde svara på alla beräkningsproblem som kunde uttryckas i kod (och som hade ett kalkylerbart svar).

En enhet eller ett programmeringsspråk anses vara Turing Complete när det kan replikera en Turing Machine genom att köra vilket program som helst eller lösa alla problem som Turing Machine kan köra eller lösa. Å andra sidan, om en enhet eller ett programmeringsspråk inte kan göra det, sägs det vara Turing Incomplete.

En enkel miniräknare är ett exempel på ett system som är Turing Incomplete eftersom det bara kan göra ett fåtal typer av beräkningar. Däremot kan en programmerbar vetenskaplig kalkylator (som kan utföra alla typer av beräkningar) betraktas som en Turing-maskin.

Blockchain och Turing fullständighet

Medan vissa tillämpningar av blockchain-teknik är Turing Complete, andra är Turing Incomplete. Detta varierar beroende på vilken skriptteknik som implementeras. Till exempel är skriptspråket som används i Bitcoin avsiktligt utformat som Turing Incomplete eftersom det tjänar sitt syfte och ökad komplexitet skulle potentiellt skapa problem. Genom att hålla det enkelt kan utvecklarna med hög noggrannhet förutsäga hur det kommer att reagera i det ändliga antalet situationer där det används.

Ethereum, å andra sidan, är byggd som en Turing Complete blockchain. Detta är viktigt eftersom det måste förstå de avtal som utgör smarta kontrakt. Genom att vara Turing Complete har Ethereum förmågan att förstå och implementera alla framtida avtal, även de som man inte har tänkt på ännu. Med andra ord betyder Ethereums Turing Completeness att den kan använda sin kodbas för att utföra praktiskt taget vilken uppgift som helst, så länge den har rätt instruktioner, tillräckligt med tid och processorkraft.