TOC Decidability Theory

Question

Which of the following problems is solvable?

a) Writing a universal Turing machine

b) Determining if an arbitrary Turing machine is a Universal Turing Machine

c) Determining if a universal Turing Machine can be written in fewer than k instructions for some k

d) Determining if a universal Turing Machine and some input will halt

Comments

yes A is the answer.We can write an universal TM.But just by checking transition moves we can't tell what type of computation it doing.There is no such algo.So option B is incorrect.

---

Can you provide any reference?

---

for universal TM you can refer this video https://www.youtube.com/watch?v=3upnsi1kFl0&index=32&list=PL85CF9F4A047C7BF7

Answer 1

An universal turing machine is a machine which can simulate any other machine. In simple words we can say, a computer which can simulate the work of any other computer.

Universal turing machine invented on the concept of "Barber Paradox". The statement says "The barber who can save all person in the town cannot save themselves". That means universal TM can accept any other machine's input other than itself

1) " Writing a universal Turing machine " UTM cannot recognize it's own action. So, it will be undecidable

2)" Determining if an arbitrary Turing machine is a Universal Turing Machine "-If a TM can simulate the work of any other TM, then it will be UTM. Here definite "yes" and "no" ans possible. So, will be decidable

3)" Determining if a universal Turing Machine can be written in fewer than k instructions for some k" By Rice Theorem we can say it will be undecidable

4)" Determining if a universal Turing Machine and some input will halt " It is halting problem of TM , which is undecidable

Refer :http://web.mit.edu/manoli/turing/www/turing.html

Comments

what is meant by "writing a Universal TM?" Please say in kids language.

---

The question is from SBI ibps exam. My friend said no explanation is given for the given answer (option A) in his book and hence was asking.

Is the question wrong?

By writing, I guess they mean by coding up TM? The link in the answer says so. Though the code that mit guy wrote is Greek and Latin for me. :p

Please guide :)

---

SBI is using TM :P

yes, it should mean coding a Universal TM which is possible.