universell Turingmaskin

en Turingmaskin som kan ersätta alla andra Turingmaskiner. Eftersom en Turing­maskin närmast motsvarar ett datorprogram är en universell Turingmaskin en maskin som kan ersätta alla datorprogram. Den motsvarar därför vad vi kallar en dator. När man talar om ”Turingmaskiner” menar man ofta universella Turingmaskiner, men det är alltså skillnad. (Observera att Turingmaskiner är teoretiska konstruktioner – det finns inga praktiskt användbara Turingmaskiner, så som de beskrevs av Alan Turing, utom för mycket enkla operationer.)

[datorvetenskap] [ändrad 6 juni 2017]

Dagens ord: 2020-09-21