I was reading this answer about Turing machines and it refers to a bussiness-card-sized one, which claims to be a universal Turing machine, based on this paper. However, I don't understand the logic of that particular machine. I understand that in a universal Turing machine the "program" is just another machine encoded in the tape of the universal Turing machine. But, how is it encoded in this case? How would you write a program that adds two numbers for this machine, for instance?

  • $\begingroup$ Have you understood how UTM(4,6) in that paper is a universal Turing machine? Can you write a program that adds two numbers for UTM(4,6)? If not, those questions should probably be asked first. $\endgroup$ – John L. Dec 23 '18 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.