Computing - Turing Machines

3 min read
What two parts does a Turing machine consist of??
  • A tape that can be read and write
  • A controller that determines what happens at each cell
How long is the tape in a Turing machine??

Infinitely long.

What are the three states of a cell on some tape in a Turing machine??

$1$, $0$ or blank.

In a Turing machine, what moves along the tape??

A read-write head.

What state must a Turing machine have??

A halting state.

In a Turing machine, what is a controller??

A finite state machine which tells the machine what to do next.

What are the three things a Turing machine can do in any one state??
  1. Read any symbol on the tape
  2. Erase or write a new symbol
  3. Move the head left or right by a single space
In a Turing machine, what are the three parameters of a finite state machine??

Input, output, head movement.

Describe the 3 steps of the state transition $0,0,L$ for a Turing machine??
  • A zero is inputed
  • A zero is outputed
  • The head moves left
What symbol is used to represent a state transition function??

$$ \delta $$

Why is $\delta$ used as the symbol for the state transition function??

Because it means “small change”.

What is the general pattern of a state transition function??

$$ \delta(\text{current state, input}) = (\text{next state, output, head move}) $$

What is a transition function??

A way to represent the transition arc between two states on a state transition diagram.

What does $\delta(S7, 1) = (S3, 1, R)$ mean??

If on state $S7$ and a $1$ is inputted, transition to state $S3$, write a $1$ and move the read-write head to the right.

PHOTO TRANSITION FUNCTION EXAMPLE For the input of $0$, what is the state transition function??

$$ \delta(S0, 0) = \delta(S0, 0, R) $$


Why is a Turing Machine useful??

Because the mathematical definition of a Turing machine defines what is computable.

Why is a Universal Turing Machine used??

Because otherwise a Turing machine would be needed for each operation.

What is the main difference between a Universal Turing Machine and a normal Turing machine??
  • Turing machines have one specific purpose
  • Universal Turing machines can be configured for different problems
What two things does a Universal Turing Machine read??
  • The definition of a Turing machine
  • Some input data
What idea did the Universal Turing Machine lead to??

The stored program computer.

What is a stored program computer??

A computer where the program andi ts data were stored in memory.

What kind of architechture is a stored program computer??

The von Neumann architechture.

Why is it not possible to create a Turing machine that solves the Halting problem??

There is no algorithm that solves the Halting problem.

Why is a Turing machine technically more powerful than any actual computer??

Because it has an infinite amount of memory.

date: 2021-01-13 10:04
- '@?computing'
- '@?regular-languages'
- '@?public'
title: Computing - Turing Machines