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??
- Read any symbol on the tape
- Erase or write a new symbol
- 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.
For the input of $0$, what is the state transition function??
$$ \delta(S0, 0) = \delta(S0, 0, R) $$
2021-01-04
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.
Backlinks
Metadata
date: 2021-01-13 10:04
tags:
- '@?computing'
- '@?regular-languages'
- '@?public'
title: Computing - Turing Machines
