ExamCompetition Your Success, Our Mission
Login Register
Question discussion

The halting problem for Turing machines (deciding whether an arbitrary Turing machine halts on a given input) is

2577Medium DSSSB TGT Computer Science 0 replies 1 views
0

The halting problem for Turing machines (deciding whether an arbitrary Turing machine halts on a given input) is

  • Adecidable by a deterministic Turing machine
  • Bnot even semi-decidable (not recursively enumerable)
  • Cdecidable only if the Turing machine is non-deterministic
  • Dundecidable, although it is semi-decidable (recursively enumerable)
Correct answer: D

Explanation

Turing proved by diagonalisation that no algorithm decides halting for all machines and inputs, but the problem is semi-decidable because simulating the machine eventually reaches a halt whenever it does halt.
Join the discussion Report an error

Discussion 0

Nobody has replied yet. Start the discussion!