# Shared Flashcard Set

## Details

Chapter 12 Terms
Invitation to Computer Science (5th Ed.)
18
Computer Science
05/05/2012

Term
 Model
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
 Turing Machine
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
 alphabet
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
 Turing Machine Program
Definition
 a set of turing machine instructions to allow a turning machine to carry out a certain task
Term
 state diagram
Definition
 a visual representation of a turing machine algorithm, where circles represent states, and arrows represent transitions from one state to another
Term
 bit inverter
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
 odd parity bit
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
 unary
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
 incrementer
Definition
 machine that adds 1 to any number
Term
 church-turing thesis
Definition
 if there exists an algorithm to do a symbol manipulation task, than there exists a turing machine to do that task
Term
 computability
Definition
 turing machines define the limits of what can be done by symbol manipulation algorithms
Term
 uncomputable/unsolvable
Definition
 no algorithm or turing machine exists to solve the problem
Term
 halting problem
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