Decidability: Questions
For each of the problems below, indicate whether it is decidable or undecidable and prove your answers.
- Given a TM T, does it ever reach a state other than its initial state if it starts with a blank tape?
- Given a TM T and a non-halting state q of T, does T ever enter state q when it begins with a blank tape?
- Given a TM T and a non-halting state q of T, is there an input string x that would cause T to eventually enter state q?
- Given a TM T, does T eventually enter every one of its non-halting states if it begins with a blank tape?
- Given a TM T, is there an input string that causes T to enter every one of its non-halting states?
- Given a TM T, does it accept the empty string in an even number of moves?
- Given a TM T, is there a string it accepts in an even number of moves?
- Given a TM T and a string w, does T loop forever on input w?
- Given a TM T, are there any input strings on which T loops forever?
- Given a TM T, does T halt within 10 moves on every string?