Problem 32
A palindrome is a string of characters that reads the same forward and backward, such as radar or IUPUI. Write a Turing machine to decide whether any binary string is a palindrome by halting with a blank tape if the string is a palindrome and halting with a nonblank tape if the string is not a palindrome. Note: The world's longest single-word palindrome is the Finnish word for "lye dealer": Saippuakivikauppias Other palindromes include: Slap a ham on Omaha pals Do geese see god A man a plan a canal Panama Recall from Chapter 11 that the job of the parser in a compiler is also to recognize strings that match patterns, where the patterns are given by means of a grammar expressed in BNF notation. Exercises 33-36 use BNF grammar notation.
Problem 33
The following BNF grammar defines a set of binary strings.
\(\langle\) string \(\rangle::=\langle\) one \(\rangle \mid<\) one \(>\langle\) string
\(\rangle\)
Problem 35
The following BNF grammar defines a set of binary strings.
\(\langle\) string \(\rangle::=\langle\) zero
\(\rangle\langle\mathrm{A}\rangle\langle\) zero \(\rangle\)
\(\langle A\rangle::=\langle\) zero \(\rangle\langle B\rangle\langle\) zero
\(\rangle\)
\(\langle\mathrm{B}\rangle::=\langle\) one \(\rangle\langle\mathrm{B}\rangle
\mid<\) one \(>\)
\(<\) zero \(>::=0\)
Problem 36
The following BNF grammar defines a set of binary strings.
\(\langle\) string \(\rangle::=\langle\) zero \(\rangle\langle\) one \(\rangle
\mid\langle\) zero \(\rangle\langle\) string \(\rangle\langle\) one \(\rangle\)
Problem 37
Your boss gives you a computer program and a set of input data and asks you to determine whether the program will get into an infinite loop running on these data. You report that you cannot do this job, citing the Church-Turing thesis. Should your boss fire you? Explain.
Problem 38
What is the significance of the unsolvability of the halting problem?
Problem 40
The 10 -step halting problem is to decide, given any collection of Turing machine instructions, together with any initial tape contents, whether that Turing machine will halt within 10 steps when started on that tape. Explain why the 10 -step halting problem is computable.
