A language is undecidable if there is no Turing Machine that will recognize that language and halt
Fantastic news! We've Found the answer you've been seeking!
Question:
A language is undecidable if there is no Turing Machine that will recognize that language and halt on all inputs. Show that the following language is undecidable: A = {M | M is a Turing machine that accepts exactly all the odd length strings} The intended solution is to reduce from the halting problem, which we will show is undecidable. The halting problem is given a Turing machine M and an input w, decide whether M terminates when given w as input.
Related Book For
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen
Posted Date: