# Finite State Machines / The Turing Machine Flashcards

What is a finite state machine and why are they useful?

- An abstract model that has a finite number of states and can only be in one state at a time
- They’re useful for recognising logical sequences
- They can model a range of problems simply

What is a finite state machine with no output called?

A Finite State Automaton (FSA)

What is a state transition diagram?

A visual representation of a FSM

uses circles and arrows

How is a state represented in a FSM?

How is a transition function represented in a FSM?

How is the starting state represented in a FSM?

How is the target state represented in a FSM?

A state is represented by a circle and a name that identifies it : S0, S1, S2 …

A transition is represented by an arrowed line and the input that makes this transition: 0, 1 or A, B, C, D

The starting state is represented with an arrow pointing towards it

The target state has a double circle around the name that identifies it

What is a state transition table?

It records all the states and transitions possible for a specific FSM

What is a mealy machine?

- A mealy machine is a finite state machine whose output is determined by its current state and the current input.
- no more than one transition is possible at a time

How does a mealy machine show what the inputs and outputs are?

Along the transition line it will show two characters or digits : a/b. a is the input and b is the output. a and b can be anything from a number to a letter to a word.

What can mealy machines represent?

Can represent electronic circuits and bitwise operations.

Can carry out an XOR function

They have a range of uses such as traffic light control and vending machines.

Describe the Halting problem

It determines if a program will halt (1 mark)

For a specific input (1 mark)

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

The Halting problem is non-computable, there is no algorithm that solves the Halting problem

State three components of a Turing machine.

- The finite alphabet of symbols that it can use
- Infinite tape
- Finite set of states
- A set of transition rules;
- A read-write head
- Start state
- an accepting / halting states

Explain what a Universal Turing Machine is.

- Instructions for TM and the TM’s input are stored on the UTM’s tape
- A Turing machine that can execute the behaviour of any other Turing machine // can compute any computable sequence

Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?

Because it has an infinite amount of memory/tape;

What are transition rules?

Rules that describe what a finite state machine should do given certain input.

What do mealy machine state diagrams not have?

A target state