Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Tag Info

## Hot answers tagged undecidability

3

If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word. So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. ...

2

Original Question: $L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}$ $L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$ prove that $L_2$ is undecidable. Answer: For first part you are correct. First language $L_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$. ...

Only top voted, non community-wiki answers of a minimum length are eligible