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.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 446
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,485 questions

42,741 answers

121,445 comments

42,135 users