Enumerators, Theory of Computation, CSE, GATE Video Lecture - Computer Science Engineering (CSE)

let us see one more concept called
enumeration machine I can say it is one
more variation of Turing machines also
known as enumerated let me define that
so like during machine you have some
semi infinitive but initially so there
will be left hand marker followed by are
blank symbols that means shall no input
yes
so here enumeration machine won't take
any input because it is not that kind of
machine which takes input second thing
you will be having you know Sigma and
tau where Sigma is output alphabet which
is used to output some symbols and tape
one form it is down like we have input
alphabet and tape alphabet in Turing
machine apart from that everything is
same so your during machine generally
will have finite control right that
means it will have some core similarly
here also this enumeration machine is
also going to have finite control that
means it is going to have a code
followed by set up States everything now
let us say your Turing machine is
starting always generally your Turing
machine starts like this right here also
this enumeration machine starts at left
hand marker okay at some start status
and one more thing generally Turing
machine will have final state and reject
state right
but here there is no final state
rejected so then how this enumeration
machine accepts it is not a kind of
acceptance machine it is going to
generate strings so your during machine
accepts input this enumeration machine
generates input/output okay that is the
difference now I will explain how this
enumeration machine is going to work in
initially in the early morning your
enumeration machine starts it is some
start state okay after that by seeing
the finite control it will have some
list of code right based on the code it
will manipulate some of the tape symbols
okay a something in that way depends on
the code then occasionally it will write
something on output tape like this a b
b:a okay so in that way then eventually
after some point of time it will
to a special state called enumerated
state so when it comes to a numerated
state that means we should understand
that one string is generated by this
Turing machine as an enumeration machine
so we have to immediately note it down
I'm just telling I mean says I'm just
kidding so after some time so this once
this string is generated for us you know
after some point of time it will be
arranged automatically that means one
string is generated after some fraction
of seconds let's say this tape will be
emptied again that means it will be
erased all the content will be erased
then this tape will start again from
fresh now your generator or enumeration
machine will go to again start state and
it will do whatever you know it will
otherwise it will continue its process
okay so after that again your
enumeration machine will write some
input here a baby bee bee a bee
something then it will go to again
enumerated State when it comes to
enumerated state again that means that
we should understand that enumeration
machine again output one more string so
that means your enumeration machine
generated one more output in that way so
once it is done again it will be erased
then your enumeration machine will
continue the process and one more thing
you remember once it comes to enumerated
state then once output is generated it
will go to start state again then it
will continue the process okay so this
is called enumeration machine so this
enumeration machine is going to generate
the strings correct so it will be if
there is easier in here no there is no
end it will be continuously generating
the strings now let me define this
enumeration machine formally enumeration
machine is represented like this it is
going to generate a language generate
Turing machine accepts a language this
enumeration machine is going to generate
a language the language generated by
example let say this machine is
the language I mean the strings which
are generated by this enumeration
machine is called language of G okay
generally language of Turing machine is
nothing but strings accepted by a Turing
machine here language of this
enumeration machine is nothing but
strings generated by this enumeration
machine sir we have a question what is
that this enumeration machine let's say
generates a language is it equivalent to
some Turing machines are accepted
language yes so there is an equivalence
whatever this enumeration machine
generates we can have a Turing machine
such a whether the Turing machine
accepts them second thing if you have a
Turing machine which accepts a language
let's say this is a language accepted by
Turing machine then definitely there
will be one generated otherwise an
enumeration machine which is going to
generate them okay there is a one-to-one
correspondence that means set of
generators are equivalent to set of
Turing machines I can say otherwise
for every Turing machine there will be a
enumeration machine for every
elimination machine there is a Turing
machine so curing machines and
enumeration machines are equivalent with
respect to expressive power if a
language is accepted by Turing machine
then the same language can be act
generated by your generator and if a
generator generates any language then we
can design a Turing machine which can
accept this I mean which you can accept
the same language understand so that is
one thing you should remember finally
generators otherwise enumerators
equivalent to Turing machines okay now
we'll see an interesting story which is
related to enumerators so only we know
that Turing machines are equivalent to
generators are enumerated right so we
are going to prove you know one of the
aspects that means I'm going to prove
that for every Turing machine we can
have a generator which is equivalent to
that okay I am going to explain that
with this story assume that let's say
raju is it during
okay so he's accepting some language
let's call it as zero star something so
language of Roger is zero star just for
our imagination so then the problem is
Roger is so arrogant and he's claiming
that I have a complicated dueling
machine and in the world there is no
generator for it but we know that for
every Turing machine there is a
generator but Raj is not accepting what
we have to do is we have to teach him a
lesson and we have to prove that for
Rogers Turing machine also there is a
generator okay now remember one thing
what is the similarities between
generator and Turing machine Turing
machine can if you can write a code in
Turing machine like you know Q on a
something q1 comma B comma right then
the same thing we can do in a numerator
and so the only difference what is the
difference between Turing machine and
enumerator a numerator cannot take the
input okay
apart from that and enumerator generally
cannot have final state and reject state
then how it is going to generate we will
see apart from that coding part if you
see the code like you know transition
function we have in do Turing machine in
generate run so we have transition
function
everything is there other than remember
one thing what we don't have is input
what we don't have is final state and
rejected apart from that everything is
safe and what we have during machine
doesn't have is Turing machine generally
whenever input is given it accepts it
correct but enumerator
it won't take input but it can generate
that you know strings in a separate
state called a sorry separate term tape
called output it and it is going to at
that time enumerated state that means I
can say your enumerator has a enumerated
state and Turing machine has final state
okay in that way these two are having
the similarities now we are going to
generate a enumerator for this Turing
machine Raja says that there is no
enumerator right I am going to show that
simple what you do is so this enumerator
and we are going to build
we know that enumerator generally
contains two tapes correct one is
working tape on which we are
to do the processing this output tape is
to generate all possible strings right
so we are going to use this output tape
only to output it's like a computer
screen we use it for outputting
something let's begin what we do is we
copy Rogers Turing machine code okay
through already I told you through
finite control we can copy in one you
know we can remember the code of another
Turing machine did you remember Ali I
told you you have a Turing machine one
you have Turing machine too then Turing
machine two can be designed such a way
that it can remember Turing machine once
code in its finite control right so
already I told you and if you have any
questions please ask me so then I can
explain you through the forum okay now
so with that capacity or capability so
your generator is like a Turing machine
right so it is going to first what it is
going to do in the high level I will
tell you on it's working tape raju
stirring machine code will be copied
okay assume like that
so rogers turing machine code we copy
here and here but what sir we don't take
input right then how you accept anything
i will tell you so further we are going
to generate first all possible strings
in the world example let say input
alphabet is Sigma is 0 1 therefore Raju
example instead as you said I accept 0
star but for that we don't have input
right first I write all possible inputs
epsilon 0 1 0 0 to differentiate
correctly so what we are going to do is
we are going to cleave hash in between
them ok assume that hash is also one of
the possible symbol on our tape alphabet
so first epsilon then hash 0 a hash 1
hash so these are the possible strings
in the world 0 0 has 0 1 in that way now
what is our job is we simulate this
Turing machine code whose tuning machine
code is this one Rodgers during machine
code on this input epsilon will ask my
dear Raju if I run you on epsilon will
you accept it
then Roger steering machine code will be
because it's a copy pasting right then
it has to be run and when Rogers during
machine code is simulated then epsilon
let's say is because definitely Roger is
going to accept epsilon then we are
going to print that on output epsilon
then after that we will go to zero we
ask Rogers during machine code
indirectly we are using Rogers to the
machine code only then exactly so Roger
accepts zero then we output zero in that
way finally all that strings of zero
star can be outputted right so finally I
can say that for this Turing machine
there is a generator exactly whatever it
is accepting we can generate but there
is a major flying method this method of
course we can do it but the method
whatever I taught you it has some small
mistake what is that I will tell you
example let's say Roger steering machine
is little bit tricky to imagine what it
is doing is we'll see first of all I
asked on epsilon my dear Rogers Turing
machine code please run on epsilon and
tell me the answer do you accept then
Roger during machine code let's say been
to final state then we output it right
perfect so up to now we did correct now
after Epsilon so what is the next thing
we are going to output we are going to
take 0 on 0 we are running when you run
on 0 then definitely since 0 is part of
Rogers Turing machine that means accept
accepted language so definitely this
Roger steering machine code is going to
heart because it has to accept and it
will accept because it will not go go to
infinite loop agree then after finite
amount of time 0 will be accepted by
your Rogers tuning machine code hence
your generator is going to generate such
a way I'm planning the generator ok so
if you have any questions about
generator survive generator is doing
like this only do I mean accept exactly
like Roger that means to generate all
the strings which are accepted by Roger
after that you know complication comes 1
then your generator is going to take 1
and it is going to simulate Roger
stirring machine now did you remember
the generally Turing machines property
whenever you give invalid input that
means
input which is not part of the language
which distorting machine accepting
example raju steering machine is
accepting zero stuff for that we have
created a Turing machine that may not be
total Turing machine what an input one
if this during machine goes to infinite
loop such a way let's say also planned
it then really if you run your drive is
Turing machine and one then you will be
in loop sir whenever we realize that we
are in loop then we terminate but that
is a problem
we never know that we are in loop
because there is no difference between
simple running and loop right so
infinite loop cannot be detected we
always think that still you know your
Turing machine is working on the input
correct properly so that's why we can at
any point of time we can't say whether
one is accepted by raju or not now we'll
ask Raju Raju
do you accept one let's say he is a
little bit this kind of Turing machine
right Raju says I don't know I'm running
don't ask me it is too early to say that
okay ask after fires after fires ask
Raju Raju
I am simulating you on input one tell me
do you heart do you go to final state I
don't know anything but since fires I'm
working maybe there is a progress so
after fires if you ask it is too early
for me asks after some time let's say
you waited for dinners then after dinner
as you asked my dear Raju
do you accept one currently I did not
accept currently I did not go to reject
state also try to understand that means
I am looping but if you assume that it
is infinite loop then I cannot do
anything because that may not be
infinite loop okay so in that way always
Raju can postpone what I want to say is
so if really after two days
still let's say Raju is looping then if
you assume that Raju has infinite loop
you may be doing mistake why let's say
after two days you declared that that
means only for two days you simulated
Raju steering machine on one after that
you declare that Raj
is an infinite loop and you rejected the
string but what can happen after two
days there is a chance I am telling so
Raju can claim like this why why did you
stop me after two days actually after
three days only I can accept that input
but after two days you simply rejected
that means after two days you simply
said that I cannot accept that is wrong
in that way so whenever you terminate
the Turing machine so you may get you
know contradictory things correct that
is a problem sir I do one thing I wait
for 50 years on some input I ask Raju
mean idea rather you accept one are not
then after 50 years still that Raju is
let's say in loop then I declare it as
infinite loop you are wrong again
maybe after sixteen years he may heart
who knows that's why can you say it 50
years after 50 years that Raju accepted
something ah rejected something No so
that's fine what I want to say is really
at any point of time Raju accepts Raju
goes to final state we can say that Raju
accepts it at any point of time Raju
goes to reject state then you can say
Raju rejected it but by not going to
final state T and by not going to reject
state it's a rather he's in some
intermediate state let's call ie
and now time is fifty years he ran for
fifty years then still I can't say
anything you should don't say it is
infinite loop may not be infinite loop
don't say he will accept may not he may
not accept don't say he will reject he
may not reject he may accept anything
can happen so that is one thing sir
then what should I do since ten years I
am running this Rajas code a lot - I
mean so many strings I have to accept
still there are infinite strings now
there is I am afraid that you know I
mean infinite loop yes that is that is a
problem so you are in a trap now no one
knows whether it is the infinite loop
partners see this is your generator
situation it is looping but we can't say
it is loop because all I experienced
that example right so funny
two years three years four years after
forest we can't say after five years we
can say after thousand years we can't
say maybe for some inputs you're Turing
machine takes 2000 years and it gives
output who knows that's fine so we
cannot say that you're Turing machine is
looping that's the problem that's why
you know raju is laughing you see
correct so how to generate a generator
which can but we should because really
you are a generator for this Turing
machine if you are in infinite loop let
say really one on one I am just telling
possibility on one let's say Rajesh
Turing machine really goes to infinite
loop then is if not mistake from raju
said sir no because Raju said he accept
zero star for every input of his
language that means zero zero zero
epsilon
triple zero definitely he will accept he
will not go to infinite room but for
other inputs like one he has to reject
for such inputs he may reject it
otherwise he may go to infinite loop so
that is a property of a Turing machine
okay so you tell me what to do the only
thing what we can do is effectively
eliminating okay so that is called
effective enumeration finally our
problem is really you want to prove that
for Rogers Turing machine we have a
enumerator then we should not stuck on
one input correct but we don't know what
input is the right input correct so we
don't know maybe there are some inputs
which are not accepted by Raju but we
don't know without running them so sir
which input we should not consider no
it's not like that correct so on every
input there is a danger so what we are
going to have is effect to enumeration
we will see how to effectively enumerate
such a way that we can have an
equivalent to regression okay let me
tell you that so what we do here is we
design in a different way rather than in
a traditional way so the idea is first
of all as it is we generate all possible
strings Epsilon okay so this is your
enumerator enumerator will have working
tape on working tape imagine multiple
tracks for our convenience so on one
track first there will be a turing
machine code
let's call this is during machine Raja
score and this is all possible strings
epsilon and zero hash one and zero zero
so okay so rather than running linearly
how we run is we run in a clever way
that means using a round robin lake in
operating system we'll be learning in
process scheduling so we can schedule
the you know inputs in a round robin
league way okay some amount of time
otherwise also known as time sharing we
give some time by epsilon in within the
time limit if it is not accepted by
roger score it doesn't mean that it
rejects but we postpone the decision
that means we don't run epsilon and
Rogers during machine we will go to zero
after that after some point of time
we'll go to one in that way I will tell
you the technique in a pictorial
representation well you understand the
idea but you don't know what is the
order we have to run our inputs so that
we can affect you to enumerate all the
strings which are generated by or which
are accepted by module further what we
can do is so let's these are all your
inputs epsilon 0 1 0 0 0 1 1 0 1 1
rather than you know looping on
particular input we don't give that
chance to you know that code what we do
is we run let say one step epsilon one
step then we run one step epsilon second
time one step zero try to understand so
that means first step on epsilon second
step and epsilon third step on 0 next
time
the fourth step will be again you know
here one step here one step here one
step here now can I say one thing
1 2 3 4 5 you know 6 after sixth step
that means at sixth step this got chance
right similarly 7 0 0 gets chance so 0 0
gets chance at this step see after that
again we'll come back and we give one
step here one step here one step here
one step here so try to understand the
procedure
first step is for Epsilon second step is
for Epsilon third step is for zero then
fourth step 50 step sixth step for
epsilon 0 1 then 1 2 3 4 5 6 7 8 9 10
steps for these 4 inputs then again come
back and give one unit one unit one unit
1 unit 1 unit 2 first to 5 inputs then
give next steps to first to 6 inputs in
that way every time there is a progress
so 6th input also getting chance
eventually correct so if you follow this
process then everyone gets you know time
to be executed correct so there is no
danger of infinite loop why we go to
infinite loop we never goes to infinite
loop right eventually now let me repeat
the process like this give terms step
one step two step three step four Step
five step sticks okay
then step 7 step e 8 step 9 step 10 now
11 12 13 14 15 then 16 step onwards this
time 4 1 2 3 4 5 6 inputs 16 17 18 19 20
21 next twenty one twenty two twenty
three twenty fourth step 20 50 step
twenty six step twenty seven step in
that way so we are covering all the
inputs so are no input we are looping
then eventually really example it says
zero zero takes only 50 steps then we
will be gaping you know this zero zero
50 steps in the next iteration it will
get one more step in next iteration it
is going to get one more step in that
way so finally we are going to cover
every input and I mean any number of
steps right finally sir example it's a
one zero requires one crore steps then
only you know that can be accepted are
you going to give yes definitely this
method if you follow because in the next
iteration again we are covering this one
zero one more time next step one more
time in that way rather than giving it
particularly for one input all the time
we are covering round robin link so that
even
only after sometime maybe there is a
delay but definitely so that is not
infinite delay after sometime one zero
is going to get 1 crore steps eventually
so really it is a part of this during
machine really Roger accepts it then
after 1 crore steps he will accept it
then we generate it that's why there is
no string which is accepted by Raju
which is not generated by us correct
definitely examples are there is a
string called 0 0 1
Raju accepts because on 0 0 1 we are
simulating Raju stirring machine correct
how many steps any number of steps also
if he takes 500 steps we are running
fibro steps but not in a1 stretch I can
say in interleaving way so definitely
every string will be generated here
effectively we are getting chance now
sir there is an input 1 on which let's
say reality whirring machine goes to
infinite loop then here also we are
going to infinite loop right but we are
not struck in correct we are definitely
having progress and we are definitely
generating the strings which are
accepted by Raju but for other inputs
still we have looping that's why so this
is called effective enumeration right
but remember one thing one important
property of this one is remember
whenever there is a recursively
enumerable language let me tell you
clearly Turing machine generally accepts
a language called recursively enumerable
correct so whenever you have a
recursively enumerable language but not
recursive for that there is no total
Turing machine possible correct for such
kind of languages then what is not
guaranteed is generally so the odd I
mean the generator cannot generate
elements in a particular order that
means so in simple words I will tell you
like this
raaah there is a largest Turing machine
and it is accepting them language let us
contra curse-free enumerable act ways so
whenever you have a recursively
enumerable language for that we cannot
have a generator which generates strings
in a lexicographic order that might not
be possible sometimes it may be possible
sometimes might not be wiser a
example see this one we definitely need
an effective procedure correct we can't
run past epsilon after that zero after
that one correct we have to give in a we
have to run in a time-sharing manner
when you run in time-sharing manner
assume that let's say zero takes five
steps on this Turing machine but you
know zero zero takes only one step then
which one will be generated first two
zero zero that means are we generating
in this order epsilon then zero then
zero zero no we are generating in a
random order correct depends on the
number of steps that takes but remember
one thing really you have let's a
recursive language then for such kind of
languages we can have a enumerator which
can print in a lexicographic order we
will see that but remember two things
now you have a recursively enumerable
language for that effective enumeration
is possible that means we are
effectively eliminating we can enumerate
on but lexicographic order cannot be
guaranteed because you know we don't
know which string is taking less number
of steps which string takes more number
of steps example one string takes only
five steps that will be quickly printed
though it is not in the order correct so
lexicographic order means so printing
epsilon first then zero plus then zero
zero I am talking about Roger Turing
machine example it says zero star is one
language printing the strings in
lexicographic order means epsilon then
zero then zero zero then triple zero so
on but in this technique really if you
use this technique sometimes we need it
also but to avoid the infinite loop then
in that model so I may not freedom to
generate the strings in this order
sometimes what can happen if your Turing
machine is designed such a way that
epsilon takes hundred steps zero takes
only one step then eventually zero will
be printed first because it will finish
it starts first after that Epsilon it is
like you know process scheduling in the
operating system you have shortest job
and you know longest job so in round
robin lake fashion if you execute who
will be pre completely who will be
grading his job first shortest job in
the same way he ran so these are all
like jobs so whose job will be completed
first which takes less number of steps
on during machine ok so that is about
enumerated and recursively enumerable
languages no let's summarize sir I have
a recursively enumerable language that
means I have a Turing machine for a
language so for such language I would
like to have a generator which prints
the strings in a lexicographic order is
it possible always no always it may not
be possible so when it is possible when
can you guarantee please tell me I can
guarantee that means I am just talking
about guarantee okay I can give you
guarantee if your Turing machine is
total touring machine that means the
language is recursive for recursive
language I can have a generator which
can enumerate the things in a
lexicographic order sir why it is
possible I will tell you very easy see
this language which is recursive further
we have a total during machine ok
remember it for such language we can
enumerate the strings that means we can
create a numerator for this Turing
machine which can generate the strings
in lexicographic order how you say first
step what we do is we directly stimulate
epsilon first okay now I am going to
create a generator that generator will
simulate this let us say this is you
know
Ronnie's Turing machine so Ronnie's
territory machines total Turing machine
which is for this recursive language
then first of all Ronnie's Turing
machine will be simulated on epsilon
using this generator
okay so generator is simulating Ronnie
on Epsilon so eventually no time sharing
now the complete you know it is like
giving complete time to Epsilon first
so even surely since this property of
you know one thing right whenever it is
a recursive
language then we can generate a total
during machine
I assume that let's say Ronnie's machine
is total touring machine here sometimes
people do mistake whenever there is a
recursive language
then total Turing machine design is
possible it doesn't mean that whatever
the way you design a Turing machine that
will turn out that as I mean total
Turing machine is wrong okay
example let's say there is a Turing
machine for zero star zero star is
recursive language because every regular
language is recursive we know that right
so for that also we can create a Turing
machine which can loop what you do is
intentionally you create write a code
such a way that if it is a write input
accepted and whenever you know that it
is wrong input since you know that
rather than rejecting intentionally go
to loop yeah
such a way we can design that means for
every recursive language and so there
can be is ordinary Turing machine that
means so we can design which is not
total Turing machine but here what I am
doing to do is so whenever you have a
recursive language first of all I
construct a total during machine because
I can construct it order to the Machine
correct if I carefully plan it after
that now come to generator what
generator is going to do is so it is
going to simulate that Rani's Turing
machine which is total touring machine
or Epsilon since that is total Turing
machine if epsilon is part of that
language it will accept whenever it
accepts then this generator is going to
generate it let's say this is output
tape on output it generates after that
it will take the next input 0 and
simulate run is Turing machine so either
accepts or rejects if it rejects then
don't I mean output it go to another
string 0 1 sorry after 0 1 right ok and
simulate run is during machine and 1
then one accepts I mean 1 is accepted by
Ronnie then you print it in that way in
lexicographic order we can print then
some student asks are you did not print
0 why first if it really is a
lexicographic order then you have to
print 0 first write 0 is rejected by
mean we have to print only strings which
are accepted by language otherwise you
know why we have to simulate then
directly we can print all the strings
it's not like that the question is we
have to print all the strings of the
language otherwise all the strings are
accepted by
that Turing machine in a lexicographic
order it is possible there is no danger
of falling in loop because if we have it
order two-dimensionality
on that there is a there is no loop so
there is no infinite waiting so happily
we can go with one input at a time but
if it is recursively adjust you know if
you have simple Turing machine not total
then there is a chance that there is an
infinite loop then don't use this
procedure already I told you for that we
have to use effective enumeration
finally let's summarize if you have a
recursive language then we can have a
generator we can have it means all
generators won't do this okay
we can design a generator which can
print the strings in alphabetical order
our lexicographic order second thing if
we have just recursively enumerable
language but we don't know whether it is
recursive or not for such kind of
recursively enumerable language there
may be total during machine may not be
if there is no total during machine
possible for such recursively enumerable
language then effect I mean we cannot
enumerate the strings in lexicographic
order because when you try to you know
Li list out all the all of them in
lexicographic order there is a danger
that you will be in a loop for that only
technique is time sharing in time
sharing we cannot guarantee that they
will be printed in lexicographic order
because they will be printed based on
the number of steps they are taking to
get acceptance otherwise rejecters
understand so this is about effective
enumeration and generators and Turing
machines now final line so recursive
languages are definitely can be
enumerated in a lexicographic order and
recursively enumerable languages are
effectively enumerated but may not be
guaranteed lexicographic order that is
very important point you have to
remember right