Week 3 Homework

Homework Problems From John Conery's talk (his slides off course web site)

1. What is the difference between the Hamiltonian Cycle problem and the Traveling Salesman problem?

2. Which does the DNA computer solve?

3. Could it solve both?

Homework Problems From Textbook Reading

These questions are taken from chapter 3 of your textbook. I'd read the questions through first so you are doing goal-directed reading. Our textbook has a lot of verbiage and it is useful to know what you are looking for.
1. We discussed IPS, CPS, and FLOPS in class. We decided we can view them as equivalent units of measure. Some scientists in 2003 found that they could get 660 trillion calculations per second (CPS) from DNA. Assume the computer you own has a rating of 57 gigaFLOPS. How much faster is this new DNA computer than the one you own?

2. What is a bit?

3. What does Kurzweil estimate as MIPS obtainable by the brain? What is his estimate of memory capacity of the brain in bits?

4. Why does the author dis(respect) human neurons? BTW: there is an interesting argument at bottom of page 124 that claims we do not need to simulate the brain at neuron level, but at higher functional level. So no need to have models of neurons.

5. Author starts to contemplate a 2 pound rock. What is CPS of the rock? What is memory capacity?

6. Paraphrase the author's conjecture about computation and time-travel at the bottom of page 140. BTW: here is the paper that started the author down this speculative track: http://arxiv.org/pdf/gr-qc/0209061. In the conclusion, Brun even discusses the multi-verse of quantum mechanics as seen in Professor Schombert's guest lecture in class. So we are building time-travel onto quantum weirdness. Too wild.

Homework Problems From MIT Debate

The next segment runs from roughly from the 17 minute mark to the 32 minute mark. Each speaker gets to say a bit more. I'd like to focus on several things.
1. RK attempts to shoot down the Chinese Room Argument. How?

2. DG attempts to uphold the Chinese Room Argument. How?

3. RK brings in the question of whether animals have consciousness. DG rather haughtily dismisses that as "Cartesian thought" from the 18th century. This is a reference to those who follow the philosophy of Rene Descartes (Cartesians), who argued that animals had no spirit, and hence we could do what we wanted to them, e.g., cut them up. More related to our discussion, Descartes proposed a mind-body dualism. He argued that the mind was distinct from the brain/body. First look at the arguments for and against dualism here: Dualism. Then answer a couple of questions.

   3.a. Which speaker, RK or DG, would you suppose would support the dualism argument (i.e., argue for dualism) and why?

   3.b. Which for or against argument appeals to you the most and why?

Homework Problems From Turing Machines

You will need the xTuringMachine tool.

As reminder, the symbol "other" is used to indicate a default rule. A default rule is used when the machine is in the state specified in the "In State" column, and no other rule applies. For example, look at the rules below. (Note this program has nothing to do with this week's problem - only used to show function of "other" and "same".)

Suppose the machine is in state 0. If it happens to be reading an x, it will follow the first rule in the table, which tells it to write an x, move right, and change to state 1. However, if it is in state 0 and reads any other symbol, then it will apply the second rule in the table, which is a default rule. The word "same" under the "Write" column in that rule tells the machine to write the same character that it read. Without this default rule, the machine would need six separate rules to tell it what to do when it is in state 0 and it reads one of the symbols y, z, 0, 1, $, or blank.

Start the xTuringMachine tool: go to the tools folder from our course page and download it; then double-click it. Load the program seen in class from here: even-odd-right.txt.

1. As a warm-up, try the even-odd-right program with this string on the tape: xx$x. What happens?

2. Assume that a $ character appearing in a string of x's represents a character to be "censored out". Could be a bad word. Could be the name of someone we wish to not identify. I want a program that will replace all $ chars with a y char. Below shows examples starting with input string and then showing output string: xxxx => xxxx x$xx => xyxx $$$ => yyy etc.

   You can use the even-odd-right program as a starting point. Or start from scratch, whichever is easiest for you. When you are finished, save it as week3-TM-prob1. Remember: you must start on left-most character in state 0.

3. Thinking a bit about the DNA computer Professor Conery discussed, let's try a little piece from the problem: pattern matching. We know that part of DNA computing is using molecular biology to match base pairs. I suppose we could simulate this fully in a Turing Machine, but it would be hairy! Here is a simpler version: find if the pattern xy occurs in a series of x,y,$ chars. If it does, write a 1 on right. If not, write a 0 on right. Here are some examples: $$$$ => $$$$0 $xy$ => $xy$1 $xx$ => $xx$0 $yx$ => $yx$0 $yxy => $yxy1 $$x$ => $$x$0 $$x => $$x0 xy => xy1 $xxy$ => $xxy$1 (this one is tricky) etc. When you are finished, save it as week3-TM-prob2. Remember: you must start on left-most character in state 0.