Turing Machines & Computability

Question 1

What is the formal model of defining a ‘computer’?

Answer 1

• 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

Question 2

What can a CPU do per step?

Answer 2

• Read from memory
• Write to memory
• Change its state
• Change current memory cell to a neighbouring cell

Question 3

If a problem, P, is a special case of another, Q, what is unique about it?

Answer 3

Problem P is not harder than problem Q.

Question 4

Why can a special case of a problem not be harder than a general case?

Answer 4

As we can use an algorithm for the more general case to solve the special case

Question 5

What is solving some problem P with another, Q, called?

Answer 5

Reduction

Question 6

What does a problem being reducible mean?

Answer 6

It implies that the special problem is not much harder than the general problem.

Question 7

What is the definition for computability?

Answer 7

A problem is computable if there is a program which solves it.