Chapter 8 Assignment 4
Lab 8.1 Question 5
Run TM2 to completion using the play button. Compare the final version of the tape with the original tape. Do you see a pattern here? If you do, you're pretty good! In order to understand the processing accomplished by TM2 you need to know more than its alphabet, start state, and tape format. You need to know that the original tape is intended (by it's aurthors) to represent the integer 3. That is, TM2 uses strings of ones to represent positive integers. On input 111b it produces tape 1111; on input 1111b it produces 11111...now do you see the pattern? TM2 add 1 to a positive integer.
Lab 8.2 Question 1
Run each TM to completion on a variety of input tapes (just make sure the tapes conform to the prescribed format). Write down the original tape and its corresponding final tape. Then write English descriptions of what information its original tape describes, and what processing is accomplished by its rules. For TM5 and TM6, you should also try to explain what the symbols T, F, N, P stand for.
T stands for True, F stands for False, N stands for Not, P stands for Program
Page 283 Review Questions
1)What do we mean by virtual machine?
Virtual machine means something that is imaginary, it's real, but it does not physically exist.
Give a similar situation outside com0uter science, in which what you think you are seeing or doing is not actually what you are seeing or doing.
By reading a good book or a novel, one tends to place themselves into the story, living it in the imagination of the mind's eye. In one's imagination, you tend to see and do whatever the characters in the story are doing, yet in reality you are just sitting there reading the book.
2) In the black box definition of a program, why do we say that some input strings may not match any output strings?
The adopted encoding scheme to interpret the data, depends on the expected results of the input that is to be interpreted.
Can an input string match two or more output strings?
Yes, it could be interpreted as a binary code for a word, an integer, or even a picture on the given string of zero's and one's.
Is every output string matched to some input string in general?
No, there could be an empty string consisting of no zero's, or one's at all. There could also be correct and incorrect actions of the program, which is still an output of the input.
3) What definition includes more objects: the black box or the clear box?
The black box has more objects. A program could produce output forever, in which there is no string that the program matches to that output, the definition also includes all possible actions of these programs, both "correct" and "incorrect".
What is the correct definition of program?
Program is a matching from the set of all possible finite binary (input) strings to some members of the set of all finite (binary) output strings.
Page 291 Review Questions
1) Give two reasons why encodings of Turing Machines are useful.a) Encoding TM's as binary strings allows us to build a TM that accepts these coded descriptions as input.
b) If we extend the notion of encoding the objects we're working with, we can combine the defintions of programs as 1)functions of binary strings and 2) that there are some things that programs simply can't do.
2) Why is the argument in which we show that matching P can not correspond to any TM called a "diagonalization" argument?
There is a contradiction that acts so bizarrely, it can't possibly be a program. There is a possible black box matching, but no possible clear box TM program. This is a reasonable-sounding problem that can never b esolved by a program.
3) What is the Halting Problem?
The halting problem is one that has no effective procedure.
Why is it impoirtant?
It introduces a contradiction to the problem; there are many problems that are undecideable, there can not be a program that answers all possible instances. As the text says..."You can write programs to do many things, but you can't do everything with computers-in particular, it is very hard to find programs that can answer questions about programs."
Extra Credit Lab 8.4 Question 3
Multiply any binary number by 3. Make the Program.
Return to index
Return to Dean's Web Project