Turingmaskin

Turingmaskin [tju^əʹriŋ-], abstrakt beräkningsmekanism, formulerad av Alan Turing 1936.

Turingmaskinen blev en tidig teoretisk modell för en dator och spelar en central roll i teorierna för beräkningsbarhet och beräkningskomplexitet och allmänt inom den matematiska logiken.

En Turingmaskin består av en styrenhet som befinner sig i ett av ett ändligt antal tillstånd, en remsa indelad i rutor som vardera

• Författare:
• Sten Henriksson