Find a Turing machine to accept the set of nonempty

Consider the Turing machine (0, 0, 0, 0, L) (0, 1, 0, 1, R) (0, b, b, 0, L) (1, 0, 0, 1, R) (1, 1, 0, 1, R) a. What is its behavior when started on the tape ... b 1 0 0 1 1 b ... b. What is its behavior when started on the tape

Consider the Turing machine (0, 1, 1, 0, R) (0, 0, 0, 1, R) (1, 1, 1, 1, R) (1, b, 1, 2, L) (2, 1, 1, 2, L) (2, 0, 0, 2, L) (2, b, 1, 0, R) a. What is its behavior when started on the tape ... b 1 0 1 0 b ... b. What is its behavior when started on the tape

Find a Turing machine that recognizes the set of all unary strings consisting of an even number of 1s (this includes the empty string).

Find a Turing machine that recognizes the set of all strings of 0s and 1s containing at least one 1.

Find a Turing machine that recognizes 0*10*1.

Find a Turing machine to accept the set of nonempty strings of well-balanced parentheses. (Note that (( )(( ))) is well balanced and (( )(( )) is not.)

Find a Turing machine that recognizes 502n 1n 22n 0 n 06.

Find a Turing machine that recognizes 5w * wR 0 w [ 50, 16* and wR is the reverse of the string w}.

Find a Turing machine that recognizes \(\{w_1 *w_2 | w_1, w_2 \in \{0, 1\}^*\) and \(w_1 \neq w_2\}\).

Find a Turing machine that recognizes the set of palindromes on {0, 1}*, that is, the set of all strings in {0, 1}* that read the same forward and backward, such as 101

Find a bit-inverter Turing machine that replaces every 0 in a string of 0s and 1s with a 1 and every 1 with a 0.

Find a Turing machine that changes a unary string to a string of the same length with alternating 1s and 0s.

Find a nonhalting Turing machine that begins with a single 1 on its tape and successively generates strings of the form 0n 10n , n 1, that is, such strings appear every so often on the tape.

Find a Turing machine that, given an initial tape containing a (possibly empty) string of 1s, adds a single 0 to the left end of the string if the number of 1s is even and adds two 0s to the left end of the string if the number of 1s is odd.

Find a Turing machine that converts a string of 0s and 1s representing a nonzero binary number into a string of that number of 1s. As an example, the machine should, when started on a tape containing ... b 1 0 0 b ... halt on a tape containing

Find a Turing machine that, given an initial tape containing a nonempty string of 1s, marks the right end of the string with a * and puts a copy of the string to the right of the *. As an example, the machine should, when started on a tape containing ... b 1 1 1 b ... halt on a tape containing

What number-theoretic function of three variables is computed by the following Turing machine? (0, 1, b, 0, R) (0, *, b, 1, R) (1, 1, 1, 2, R) (2, *, *, 3, R) (3, 1, 1, 2, L) (2, 1, 1, 4, R) (4, 1, 1, 4, R) (4, *, 1, 5, R) (5, 1, b, 5, R) (5, b, b, 6, R)

What number-theoretic function of one variable is computed by the following Turing machine? (0, 1, 1, 1, R) (1, b, b, 9, R) (1, 1, 1, 2, R) (2, b, b, 3, L) (3, 1, b, 9, L) (2, 1, 1, 4, R) (4, b, b, 5, L) (5, 1, b, 3, L) (4, 1, 1, 6, L) (6, 1, 1, 6, L) (6, b, 1, 7, L) (7, b, 1, 8, L) (8, b, 1, 9, L)

Find a Turing machine to compute the function f(n) = b 1 if n = 0 2 if n 0

Find a Turing machine to compute the function f(n) = b n if n is even n + 1 if n is odd

Find a Turing machine to compute the function f(n) = 2n

Find a Turing machine to compute the function f(n) = b n3 if 3 divides n undefined otherwise

Find a Turing machine to compute the function f(n1, n2) = n1 + n2

Find a Turing machine to compute the function f(n1, n2) = b n1 if n1 is even n2 if n1 is odd

Find a Turing machine to compute the function f(n1, n2) = b n1 n2 if n1 n2 0 otherwise

Find a Turing machine to compute the function f(n1, n2) = max(n1, n2)

Do Exercise 21 again, this time making use of the machines T1 and T2 of Exercises 16 and 23, respectively, as functions. (Formally, the states of these machines would have to be renumbered as the quintuples are inserted into the main program, but you may omit this tiresome detail and merely invoke T1 or invoke T2.)

Describe verbally the actions of a Turing machine that computes the function f(n1, n2) = n1 # n2, that is, design the algorithm but do not bother to create all the necessary quintuples. You may make use of Exercises 16 and 23.