Automata and Computability

Let c1 xn + c2xn-1+…+ cnx + cnx + cn + 1 be a polynomial with a root at x = x0. Let cmax be the largest absolute value of a cI . Show that (attached)

Automata and Computability

Let A = (attached) R and S are regular expressions and L(R)  L(S) . Show that A is decidable.

Automata and Computability

Let A = (attached) | R is a regular expression describing a language containing at least one string w that has 111 as a substring (i.e., w = x111y for some x and y)}. Show that A is decidable.

Automata and Computability

Let C be a language. Prove that C turing-recognizable if a decidable language D exists such that C = {x | y (x,y  D)}.

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.

Automata and Computability

Describe two different Turing machines, M and N, where, when started on any input, M outputs N and N outputs M.