The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
133 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
asked in Theory of Computation by Loyal (5.4k points) | 133 views
0
ans B)?

which exam it came?
0
Given answer is A

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

1 Answer

+1 vote

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

answered by Veteran (83.8k points)
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

Please guide :)
+1
SBI is using TM :P

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,485 questions
42,741 answers
121,445 comments
42,135 users