which exam it came?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 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

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 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

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

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 :)

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 :)

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,094 questions

45,587 answers

132,148 comments

49,124 users