Flashcards in Finite State Machines / The Turing Machine Deck (26)

Loading flashcards...

1

## 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

2

## What is a finite state machine with no output called?

### A Finite State Automaton (FSA)

3

## What is a state transition diagram?

###
A visual representation of a FSM

(uses circles and arrows)

4

##
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

5

## What is a state transition table?

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

6

## 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

7

## 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.

8

## 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.

9

## Describe the Halting problem

###
It determines if a program will halt (1 mark)

For a specific input (1 mark)

10

## 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

11

## 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

12

## 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

13

## 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;

14

## What are transition rules?

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

15

## What do mealy machine state diagrams not have?

### A target state

16

## What can mealy machines be used for?

###
They can provide a simple model for:

- Cipher machines.

- Traffic lights

- Timers

- Vending machines

- Basic electronic circuits

17

## What does the Turning machine consist of?

###
- An infinitely long strip of tape divided into squares

- A read/write head

- A halting state/stop state

18

## What does a square represent in a Turing Machine?

### A square represents a blank state

19

## What notation is used by Turing machines?

###
(input, output, movement) is used.

for example (1,1,L) means if the input is 1, output 1 and move left

20

## How do Turing machines work?

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

21

## What is a transition function?

### The transition rules for a Turing Machine

22

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

###
δ (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

## What can a Turing machine represent?

### A Turing machine can theoretically represent any computation

24

## What idea did the Universal Turing Machine lead to and why was this?

###
- 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

## What must a valid identifier consist of in a FSM?

###
- Must start with a lowercase letter

- Any number of letters or numbers may follow after this

- There is no limit on the length of a identifier

26