Chapter 12 Flashcards

(8 cards)

1
Q

Function

A

Each possible input value maps to a single output value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Computable function

A

can be computed by some algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Non-computable functions

A

can not be computed by any algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Turing machine

A

tool for studying the power of computing (algorithmic processing)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Turing machine components

A
  • control unit (state and actions),
  • tape (infinite),
  • read-write head.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Polynomial problem

A

problem for which there exists an algorithmic solution within complexity class O(n x ) for some x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Non-polynomial problem

A

problem for which there exists no algorithmic solution within complexity class O(n x ) for any x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly