Turing machine
Turingi masin
olemus
arvuti matemaatiline mudel M
- A.Turing, 1936
- põhikomponendid:
(i) arvuti mälu modelleeriv lõpmatu
jadapöördusega mälu ("lint")
(ii) lõplikust arvust olekutest koosnev programm
- iga arvutuse sisendandmed x esitatakse
kodeerituna lindil ja töö käigus asendatakse
väljundandmeid y = M(x) esitava koodiga
- iga arvutust saab esitada
programmi olekute lõpliku jadaga,
mis alati lõpeb kindlas lõppolekus
piltlikult
https://www.youtube.com/watch?v=FTSAiF9AHN4
https://www.youtube.com/watch?v=vo8izCKHiF0
https://www.youtube.com/watch?v=E3keLeMwfHY
ülevaateid
https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html
https://en.wikipedia.org/wiki/Turing_machine
https://en.wikipedia.org/wiki/Universal_Turing_machine
https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine
https://en.wikipedia.org/wiki/Probabilistic_Turing_machine
https://en.wikipedia.org/wiki/Neural_Turing_machine
https://en.wikipedia.org/wiki/Quantum_Turing_machine
https://plato.stanford.edu/entries/turing-machine/