Turning Machines

Page 1

Turning machines

1. Turning decidable machines- They are the ones who either accepts and halt or reject and halt. Here halting is essential.

2. Turning Recognizable machines- They are the ones who either accepts and halt or it something is rejected then it goes into a loop.

3. Recursive languages in Turning machines are the one who is decidable.

4. Recursive enumerable is the one who is turning recognizable in nature.

Page 2

Multitape Turning Machine

Def= every multitape turing machine has a subsequent e tape turning machine

rules

1) it should store all tapes in a single tape

2) each tape has a tape head

3) one move in multitape turning machine should be updated in other tapes also

we have 3 levels and one multitape

1) dot

2)according to transition move the dots

3)then make a blank space after one shift

Page 3

non deterministic turing machinee

1) transisition function different

Q x E->P{Tx(R/L)xQ}

it says other than going on any one state, it can go on many states instead

2) Configuration

A way to represent entire state of tm at a particular step during computation

it tells about

the current state

the current tape head

entire tape contents

as we have only one move in terms of deterministic turning machine it is linear in state

non deterministic is in the shape of tree instead

look at the images

outcomes of non deterministic combination

1)accept 2)reject 3)loop

accept if goes to accept

reject if halt and reject

if doesn't reach a state and infinite loop then loop

theorem

power of non detreministic and deterministic are the same

so theaorem every non has an equivalent deterministic tm

how to change a non to deterministic

1) make three states

input tape- to take the head

simulation tape-deterministic to perform the change

address tape-what change to be made

Page 4

decidable and undecidable

recursive language- when it is only accepted or rejected

recursively enumerable language- when it accepts or halt and if reject it can sometimes halt and sometimes not.

decidable- if it is recursive language.

partially decidable-when it is recursively enumerable language

undecidable-if it not in decidable

it can be partially decidable but cannot be decidable

and it is not partially decidable then it doesn't exist a tm ie, undecidable

theorem - every tm is undecidable;e

refer universal turning machine