Chapter 12 Flashcards
(8 cards)
Function
Each possible input value maps to a single output value
Computable function
can be computed by some algorithm
Non-computable functions
can not be computed by any algorithm
Turing machine
tool for studying the power of computing (algorithmic processing)
Turing machine components
- control unit (state and actions),
- tape (infinite),
- read-write head.
The halting problem
A program is self-terminating if its execution terminates when started with itself as input
Given the encoded version of any program, return 1 if the program is self-terminating, or 0 if it is not
Polynomial problem
problem for which there exists an algorithmic solution within complexity class O(n x ) for some x
Non-polynomial problem
problem for which there exists no algorithmic solution within complexity class O(n x ) for any x