5,862 views
1 votes
1 votes
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

1 Answer

2 votes
2 votes

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

Turing Machine Schematic

Related questions

3 votes
3 votes
3 answers
1
Parshu gate asked Nov 29, 2017
610 views
Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular?