Term
|
Definition
Properties
-captures the important properties of the real thing
-probably differs in scale from the real thing
-omits some of the details of the real thing
-lacks the full functionality of the real thing |
|
|
Term
| Properties of a computing agent |
|
Definition
-must be able to accept input
-must store info in and retrieve it from memory
-must take actions according to algorithm instructions |
|
|
Term
|
Definition
-includes a (conceptual) tape that extends infinitely in both directions. The tape is divided into cells, each of which contains one symbol from the alphabet.
-The input must be expressed as a finite string of nonblank symbols from the alphabet, then it writes its output on the tape again using the same alphabet of symbols.
-the rest of it consists of a unit that reads one cell of the tape at a time and writes a symbol in that cell
-single primitive operation is to check its current state and the current input symbol being read, look for an instruction that tells what to do under these circumstances, and then carry out the three actions |
|
|
Term
|
Definition
-finite set of symbols used for a turing machine
-always contains a "b" for blank, usually both the symbols 0 and 1, and sometimes a limited # of other symbols like X and Y used as placeholders or markers of some kind |
|
|
Term
| Turing Machine (shorthand notation) |
|
Definition
| current state, current symbol, next symbol, next state, direction of move |
|
|
Term
| Turing Machine (three actions) |
|
Definition
| -each time an operation is done it 1) writes a symbol in the cell replacing the symbol already there 2) goes into a new state that might be the same as the current state 3) moves one cell left or right |
|
|
Term
|
Definition
| a set of turing machine instructions to allow a turning machine to carry out a certain task |
|
|
Term
|
Definition
| a visual representation of a turing machine algorithm, where circles represent states, and arrows represent transitions from one state to another |
|
|
Term
|
Definition
| changing 0s to 1s and 1s to 0s, for a turning machine there is only one state (one circle) in the state diagram |
|
|
Term
|
Definition
| an extra bit that can be attached to the end of a string of bits. If the string of bits has an even # of 1s, it is set to 1 so that the number of 1s in the whole string is odd |
|
|
Term
|
Definition
-means that we will use only one symbol, namely 1
-any unsigned whole # n is encoded by a sequence of n 1 1s |
|
|
Term
|
Definition
| machine that adds 1 to any number |
|
|
Term
|
Definition
| if there exists an algorithm to do a symbol manipulation task, than there exists a turing machine to do that task |
|
|
Term
|
Definition
| turing machines define the limits of what can be done by symbol manipulation algorithms |
|
|
Term
|
Definition
| no algorithm or turing machine exists to solve the problem |
|
|
Term
|
Definition
| given any collection of turing machine instructions together with any initial tape contents, whether that turing machine will ever halt if started on that tape |
|
|
Term
|
Definition
| assume that such a turing machine does exist and then show that this assumption leads to an impossible situation, so such a machine could not exist after all |
|
|
Term
| consequences to unsolvable problems |
|
Definition
-no program can be written to decide whether any given program always stops eventually, no matter hat the input
-no program can be written to decide whether any 2 programs are equivalent (will produce the same output for all inputs)
-no program can be written to decide whether any given program run on any given input will ever produce some specific output |
|
|
