# Finite State Machines / The Turing Machine Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

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

A
• 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
2
Q

What is a finite state machine with no output called?

A

A Finite State Automaton (FSA)

3
Q

What is a state transition diagram?

A

A visual representation of a FSM

uses circles and arrows

4
Q

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

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

5
Q

What is a state transition table?

A

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

6
Q

What is a mealy machine?

A
• 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
7
Q

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

A

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.

8
Q

What can mealy machines represent?

A

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.

9
Q

Describe the Halting problem

A

It determines if a program will halt (1 mark)

For a specific input (1 mark)

10
Q

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

A

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

11
Q

State three components of a Turing machine.

A
• The finite alphabet of symbols that it can use
• Infinite tape
• Finite set of states
• A set of transition rules;
• Start state
• an accepting / halting states
12
Q

Explain what a Universal Turing Machine is.

A
• 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
13
Q

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

A

Because it has an infinite amount of memory/tape;

14
Q

What are transition rules?

A

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

15
Q

What do mealy machine state diagrams not have?

A

A target state

16
Q

What can mealy machines be used for?

A

They can provide a simple model for:

• Cipher machines.
• Traffic lights
• Timers
• Vending machines
• Basic electronic circuits
17
Q

What does the Turning machine consist of?

A
• An infinitely long strip of tape divided into squares
• A halting state/stop state
18
Q

What does a square represent in a Turing Machine?

A

A square represents a blank state

19
Q

What notation is used by Turing machines?

A
```(input, output, movement) is used.
for example (1,1,L) means if the input is 1, output 1 and move left```
20
Q

How do Turing machines work?

A

They find the first blank cell on the tape, to the right of the current position of the read/write head.

21
Q

What is a transition function?

A

The transition rules for a Turing Machine

22
Q

What is the notation for a transition rule in a Turing machine?

A

δ (Current State, Input symbol) = (Next State, Output symbol, movement)
For example:
δ (S1, 0) = (S2, 1, L) means IF the current state is S1 and the input is 0, then write a 1 on the tape, move left and change state to S2

23
Q

What can a Turing machine represent?

A

A Turing machine can theoretically represent any computation

24
Q

A
• The stored program computer
• Because a Turing Machine reads (off it’s own tape) both the description of the machine to be simulated and the input to the machine.
25
Q

What must a valid identifier consist of in a FSM?

A