Chapter 12 Flashcards
(8 cards)
1
Q
Function
A
Each possible input value maps to a single output value
2
Q
Computable function
A
can be computed by some algorithm
3
Q
Non-computable functions
A
can not be computed by any algorithm
4
Q
Turing machine
A
tool for studying the power of computing (algorithmic processing)
5
Q
Turing machine components
A
- control unit (state and actions),
- tape (infinite),
- read-write head.
6
Q
The halting problem
A
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
7
Q
Polynomial problem
A
problem for which there exists an algorithmic solution within complexity class O(n x ) for some x
8
Q
Non-polynomial problem
A
problem for which there exists no algorithmic solution within complexity class O(n x ) for any x
