Turing machine

Question 1

What is a Turing Machine

Answer 1

A machine that can run any algorithm
A universal machine that executes small number of executions
Deterministic FSM with an infinitely long tape

Question 2

What is a universal machine

Answer 2

A machine capable of simulating any other machine

Question 3

Why are Turing machines important

Answer 3

Shows what is computable or not
Shows what functions can be computed
Nothing is more powerful than a Turing machine

Question 4

What does a Turing machine consist of

Answer 4

Finite set of states
Finite alphabet of symbols
An infinite tape
A read-write square that moves one square at a time

Question 5

What is the rule of a State Transition Diagram

Answer 5

symbol (read on tape)| symbol (write onto tape) , movement

Question 6

What does a transition function look like

Answer 6

δ(Current state, Input) = (Next State, Output, movement)

Question 7

What is a universal Turing Machine

Answer 7

Can execute another Turing Machine by simulating its behaviour.

Question 8

What is the halting problem

Answer 8

A question if it is possible to create a program that can determine if another program will stop or continue forever