1
vote
1answer
163 views

prove Turing recognizable

This is actually an old exam question its not my homework; Let L = { : M is a TM with an input alphabet of {a,b} and M accepts at most one word, i.e. M either accepts no words or accepts exactly one ...
2
votes
3answers
2k views

Proving that a Turing Machine that only accepts even length strings is undecidable

I need to prove that a Turing Machine that only accepts even length strings in undecidable. The proof I was thinking is explaining the following: Given an input that contains even length strings, if ...
2
votes
1answer
103 views

Where is the flaw in the following proof?

Where is the flaw in the following proof, that if a language is Turing recognizable then we can enumerate it? Proof Let $TM1$ be a Turing machine for language $L$. We can create an enumerator $E$ ...