Turing Machines & Computability Flashcards
1
Q
What is the formal model of defining a ‘computer’?
A
- They have a memory bank
- They have a CPU, which has a small amount of memory
- They have program(s)
- A CPU that operates in steps
2
Q
What can a CPU do per step?
A
- Read from memory
- Write to memory
- Change its state
- Change current memory cell to a neighbouring cell
3
Q
If a problem, P, is a special case of another, Q, what is unique about it?
A
Problem P is not harder than problem Q.
4
Q
Why can a special case of a problem not be harder than a general case?
A
As we can use an algorithm for the more general case to solve the special case
5
Q
What is solving some problem P with another, Q, called?
A
Reduction
6
Q
What does a problem being reducible mean?
A
It implies that the special problem is not much harder than the general problem.
7
Q
What is the definition for computability?
A
A problem is computable if there is a program which solves it.
