Automata and Computability

A useless state in a pushdown automaton is never entered on any input string. Consider the problem of testing whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.

Automata and Computability

Show that all Turing-recognizable problems mapping reduce to ATM.

Automata and Computability

Consider the problem of testing whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

Automata and Computability

Show that the PCP is undecidable over a binary alphabet, that is, over the alphabet  = {0,1}.

Automata and Computability (A125)

1. Give an example in the spirit of the recursion theorem of a program in a real programming language (or a reasonable approximation thereof) that prints itself out.