Notes for the AQA A-Level in Computer Science on computational thinking. These notes include information about Turing machines, finite state and mealy machines, sets and set operations, regular languages and more.
The document also includes small code snippets to support the theory. Important se...
A Turing machine is a theoretical device thought of by Allan Turing in
1936 which can carry out any computer algorithm, no matter how
complex.
What is a Turing Machine?
A Turing machine is an FSM which can read or write data (a string of
characters) to any position on an infinitely long tape according to a set of
rules.
A Turing machine has:
A finite set of states
A finite alphabet of symbols
An infinite tape with marked off squares
A sensing read-write head that can travel along the tape one square at a
time
The machine must have a start state and at least one stop state -- the
halting state
Any alphabet of symbols may be used, but we generally use only a binary
alphabet of 0 and 1 and _ for a blank square
The controller is a Finite State Machine which tells the machine what to do
next.
In any one transition, the machine can:
Read the symbol on the tape
, Erase or write a new symbol
Move the head left or right by a single space
Turing Machines can be described as Mealy Machines with a third output --
a direction.
Input/Output, Direction
Transition Function
The function that defines the transitions between states
A way to represent the transition arc
Can be represented with δ notation
Turing Machines act as a definition of what is and is not computable. It
is proven that a Turing Machine is capable of computing any algorithm.
Complex algorithms can be constructed by combining simple Turing
Machines that each solve a part of the problem.
Universal Turing Machine
A Universal Turing Machine (UTM) can simulate any TM by first reading a
description of all the TMs required to solve a problem, and then the input
required for the calculations.
Repeatability
It will faithfully execute operations on the data precisely as the TM being
simulated does.
All modern computers are based on the idea of the Turing Machine -- they
take a program and act on the input, performing logical operations to give an
, output
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller pencilcaseman. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $20.26. You're not tied to anything after your purchase.
