Turing-maskinen

Turing-maskinen er en modell for hva beregning er. Den universelle Turing-maskinen kan simulere andre Turing-maskiner Består av: • Uendeliglangtape. Deltinnicellersomhverkan romme ett symbol • Lese/skrive-hodesomkanbevegeseglangstapenog lese symbolet som befinner seg i en celle og/eller skrive et symbol der • Tilstander. Deriblant en start-tilstand. Maskinen befinner seg i 1 tilstand til enhver tid. • Transisjonsfunksjon