Shared Flashcard Set

Details

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

Additional Computer Science Flashcards

 


 

Cards

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
proof by contradiction
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
Supporting users have an ad free experience!