Artificial Minds - Homework 3

Artificial Minds - Spring 2009

Homework 3

Part 1: due by class time Monday, February 9

Read Chapter 4 of Artificial Minds, by Stan Franklin.
Read the short excerpt from Infinity and the Mind, by Rudy Rucker, which I handed out in class.
Read the essay Computer Science as Empirical Inquiry: Symbols and Search, by Allen Newell and Herbert Simon (Chapter 4 in Mind Design II).
Be prepared to answer a few brief questions about these readings when you come to class.

Part 2: due by class time Thursday, February 12

These exercises will be officially due on Thursday. However, you should attempt to do them by Monday. That way, if you get stuck or have questions, you'll have time to ask me about it before the deadline.

Here is the ABBA formal system:

Symbols: A B

Axioms: palindromes over A, B
For example, the following strings are all axioms:
```
   ABBA
   BAAB
   AA
   ABBBBBBA
   BAAAB
```
Rule: if we can make xA, then we can make Bx (where x represents a string containing any combination of A's or B's)

For example, from ABBA you can derive BABB
For each of the following ABBA-strings, derive the string as a theorem, showing each of the intermediate steps, or explain why it cannot be derived. Show your work clearly.
```
   BA

   BBAAA

   BABA
```
Here is the BZ formal system:

Symbols: B C P Z
Axioms:
```
   Z
   B
   BZ
```
Rules (in which x and y represent non-empty strings containing any combination of B's or Z's):
1. if x is a theorem then so is xPP
2. if xZPP is a theorem then so is xB
3. if xBPP is a theorem then so is xCZ
4. if xZCy is a theorem then so is xBy
5. if BCy is a theorem then so is BZy
6. if xBCy is a theorem then so is xCZy
Example: BZZ is a theorem:
```
   BZ    (axiom)
   BZPP  (rule #1)
   BB    (rule #2)
   BBPP  (rule #1)
   BCZ   (rule #3)
   BZZ   (rule #5)
```
For each of the following BZ strings, derive the string as a theorem, showing the intermediate steps, or explain why it cannot be derived:
```
   BZB

   ZBZ

   BZZZ
```
(Problem 5 from Lab 1) Create a Turing Machine that will move to the right until it finds a $. Then it will erase everything on the tape between that $ and the next $ to the right. It will halt when it gets to the second $. The $'s themselves should not be erased. You may assume that the only symbols on the tape will be 0's, 1's, $'s, and blanks. You can do this with a fairly simple machine that uses only two states. (Note that if the machine is started on a tape that does not contain two $'s to the right of the machine's starting position, then the machine will never halt.)

Write out your Turing Machine's rule table clearly and neatly.
(Problem 6 from Lab 1) Create a Turing Machine that will move to the right until it finds three X's in a row. When it finds a group of three consecutive X's, it should move back to the first of the three X's and halt there. Make sure your machine works for any strings of 0's, 1's, and X's, such as the one below:
```
0011X01XX1011X111XX00XXX00
```
Write out your Turing Machine's rule table clearly and neatly.
Describe how you could construct a Turing Machine that will move to the right looking for a particular sequence of X's, Y's, and Z's, assuming that its tape contains only X's, Y's, Z's, and blanks. For example, if it is looking for XYZZYX, it should move to the right until it has found the symbols X, Y, Z, Z, Y, and X in consecutive squares, and then it should halt. You don't need to construct the actual rules for the machine (although you can if you want), just explain its design clearly. What is the minimum number of states that such a machine would need (not counting the halt state), assuming that you don't care which square it halts on? Why?
A Turing Machine can be built to use any finite number of different symbols. But no matter how many symbols a machine might use, the same computation could be done by a machine that uses only the symbols 0, 1, and blank. Why is this true? (Think about the way data is represented in a real computer.) If this is the case, then, why bother with Turing Machines that use more than the minimum number of symbols?
Extra Credit: Find an interpretation for the BZ formal system from Exercise 2 akin to the "meaning" found for the PQ-system we discussed in class.
Extra Credit: Construct a Turing Machine to do the following: Assume that the machine is started on a tape that contains nothing but a sequence of X's and O's. (The machine must work for any such sequence.) The machine is started on the leftmost symbol of this sequence. The purpose of the machine is to separate the X's from the O's. For example, given the input XXOXOOXOXX, it will change the tape to read XXXXXXOOOO. The output string does not have to be in the same place on the tape as the input string, but it should be the only thing on the tape when the machine halts. There are many ways to make such a machine. Feel free to use the Turing Machine simulator from lab to help you design and test your answer.

Write out your Turing Machine's rule table clearly and neatly.