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 

