These are the lecture notes I created which I used to revise for the CS1005 Logic and Computation exam at Brunel University in which I received a First Class in.
Module: CS1005
Lecture Topic: Turing Machines
Week: 2
Alan Turing (1936)
British Mathematician
Developed the idea of an abstract machine that could perform logical operations. It could
read, write or delete symbols on an infinitely long tape.
Turing machine
Infinite tape: Denumerable set of locations, each containing exactly one symbol
Read-write head: can move one location left or right
A state register: stores the state of the machine
A finite table of instructions: Erase/write a symbol, move left/right/no move, go to a
new state or stay in same state.
Operation
State
Value at current tape position
Actions at each step: write a value at current tape position, move/read/write
head/change state.
1/0 represent binary numbers.
* at the right hand side of the number is the terminating symbol.
Turing Machines can calculate:
Computable numbers: a Turing machine which starting from a blank tape computes an
arbitrary precise approximation to that number.
Computable Functions: machine for addition
Universal Turing Machine: start the UTM on a tape which includes another TM, it can
simulate the TM – like a computer running code.
Turning Machines cant:
A particular TM and input determine whether it will halt or not. This is the halting problem,
a function that returns true if it halts and is incomputable.
Analogue: continuously varying value, as in analogue signal
Digital: varies in discrete steps, normally encoded as binary
,Module: CS1005
Lecture Topic: State Transition Diagrams & Turning Machines
Week: 3
Automata Theory
Automatons are abstract models of machines that performs computation on an input by
moving through a series of states or configurations. Examples of Automated Machines:
finite state machines, turing machines.
Characteristics:
Inputs: Assumed to be sequences of symbols selected from a finite set of input
signals.
Outputs: sequences of symbols selected from a finite set.
States: Finite set, whose definition depends on the type of automaton.
State Transition Diagram:
A diagram that indicates the possible states of automaton and the allowable transitions
between such states.
Circles/Nodes represent a state
Arrows represent state transitions
Each arrow also represents one instruction
An arrow is labelled with current symbol (input), new symbol (output) and direction.
Turing machine: has a date structure called an infinite tape.
The tape is divided into cells and each cell contains one symbol.
Δ denotes an empty or blank cell.
A head accesses one cell at a time, it can read/write/move left or right. The head is at the
beginning of the tape at the beginning of computation.
State Machine for Turing:
It is a Finite State Machine
It has an initial state
Final States where we stop computation: the accept and reject state
The machine may enter into a loop where we do not stop
It is a deterministic machine, every state has one transition we can take.
, A Turing Machine is a state machine but it has an infinite tape.
The programme of a TM is represented as a diagram: depending on the symbol
under the head and the state, the machine writes a symbol, moves left or right or
stays in place, and/or changes state.
Once a Turing Machine enters the accept/reject state it stops
• L=01*0 means one 0, any number of 1s, 0 at the end.
, Module: CS1005
Lecture Topic: Finite State Machines
Week: 4
Finite State Machines
The simplest model of computation
Small computer or controller: limited memory, not a lot of computational power
Not a lot of computational power
They have a start state
They can be used to accept or generate strings
• A (deterministic) finite state machine is defined by tuple (S,s1,X,Y,d,l) in which:
• S is a finite set of states and s1 is the initial state (nodes)
• X is the finite input alphabet/set
• Y is the finite output alphabet/set
• function d is the state transfer function (edges), d(S,X)=S
• function l is the output function.
• Examples of the application of FSMs:
Embedded systems
• Vending machine
• Washing machines
• Controlling lifts (elevators)
• Railway junctions
• Telephone networks
A turing machine is a finite state machine plus a tape memory.
Finite state machine is a state machine with a start date. It has limited memory.
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 cslbrunel. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.89. You're not tied to anything after your purchase.
