251 views
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
0
ans B)?

which exam it came?
0

My friend asked this question in a group.
0
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.
0
Can you provide any reference?
0

for universal TM you can refer this video

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

0
Are the number of Turing machines countable? Because only then we can say yes or no
0
countable is something different

No, how this can be countable?
0
A UTM simulates any other machine when description and Input are given to it. I was thinking like.. If we wish to determine a TM is UTM or not... It should be able to simulate all possible TMs when description and input are given. That's why I asked.
0
what is meant by "writing a Universal TM?" Please say in kids language.
0
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

+1
SBI is using TM :P

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

1