GentleRex
Induction example
Intro to Theory of Computation
Reg lang properties
Pumping Lemma
decidability and MORE..
   
 


decidable or undecidable?
decidable - is the issue of being
able to establish complete membership
, this is manifested in the ability
of a turing machine to produce a
yes or no answer with regards to
acceptance of a language. If complete
membership is not identified , then a
language - while it may be accepted by
a turing machine is deemed - undecidable
(our last category of recognizable
languages)

Can we tell if two different FA's accept
 the same language?
yes - in all circumstances - (this is
 decidable)

why?
because the FA is very limited in scope
 and does not fall into an endless loop
 on any input - it simply cannot by design
 - either you end up in an end state or you
don't - that is it.

 

can we tell if two separate cfg's accept the same
language?
no  - not in all circumstances (not decidable)
why not? - we can relate this to the halting
problem but it is too hard to bridge it alone
 - here we examine computation histories as a
 means to bridge or we can examine the PCP problem
 , or more specificially the modfied PCP problem
(that looks more like the matching of derivations)


consider the modified PCP
if you have a language in a(n-times) b(n-times) c(n-time)
language in alphabet (a,b,c) then you have a language
in which you will not be able to identify if a word
 belongs in two cfg languages as they could not
 be identified, as if they could then they would
be in both languages (or re-iterated if they could be
 identified (a sub-languagewith non-context free 
properties) then you also solve the halting problem.


 

 

 

 

To put our issues of recursive/ decidable vs.
recursively enumerative in context consider what
we define as countable:
A set A is 'countable' if either it is finite or
has the same size as N
'N' in this case refers to the set of natural
numbers or even natural numbers in which you
can pass into a function and determine a corresponding
number and end up with a set that is just as big
as this infinite set 1,2,3...
There are larger sets than this set - this is
what we refer to as 'uncountable' which supports
our concept of undecidable
this is demonstrated via diagonalization.
Diagonalization is a way of expressing a very very
large set of numbers by demonstrating that you can
have a huge (infinitely huge) matrix in which
if you take the diagonals and make them unique
you in turn have identified yet another number of
equal size that is not in your set!
this is larger than the set of natural numbers
and we can prove that as in taking even a binary
representation (of course working with more than
a binary representation can generate even larger
infinite sets.


consider a matrix of 4X4 of unique binary numbers


1000
0100
1010
0011

 

they can be anything! as long as they are binary and
unique.
Consider the diagonal
1111
now invert the bits
0000
you now have a string that is not in any of the four
strings

why?
well for t1 it cannot exist since its first digit is different
cannot exist for t2 as the second digit is different
same t3,t4 ... and on and on.

actually four binary digits are countable (as integers
or binary values)
any statistican can tell you there are only 2 pow(4)
combinations.

in the 'N' set you can count to 9999 or ten thousand
digits (countable!)


BUT- towards real numbers or 'R' is uncountable as
you can use this principle to demonstrate that
there are many more (infinite) combinations in the
range of 0-1 in which these cases show only two examples
in the range of natural numbers


N (NOT equivalent to)  'R'

R > N

 


back to demonstration
consider


1000...
0100...
1010...
0011...
....
....
....

 

infinitely rows and columns and you will have
an exponential infinity (or a much larger
infinite set)


Hence R is undecidable.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DFA
m
01
0101
010101
nm
111
101
110
000


Wait. can't a DFA take in the same numbers?
and tell you whether it is in or out?
(think - this is a yes or no question!)

TM cannot (cannot be decidable....)   while DFA can!
(why - the book said so!)
(acually TM can too... but it is only recognizing
the language and not guaranteed to halt on all input)


ok. why?
since the DFA is in recursive category-
goes hand-in-hand with the memebership algorithm

the proposal was oversimplified (especially
in the context of the TM being applied towards
regularity...kind of like 'solving' an easy
solution to p.l. when the point of the matter
was that all examples must be applied - that's it
one difficult problem to solve and you have
an answer.


Since TM can recognize languages that
ultimately cannot be solved... (if you want
to know better - review the halting problem
which is supported by diagonalization.) you can
actually find out what is in the regular language
the HARD part is determining what part isn't
due to the fact that the TM will keep working
on difficult problems - i.e. recognizing them
BUT NOT SOLVING THEM - makes the TM - reg
undecidable

by reducabilty if you could - then in turn you could
solve the A-TM which is what all of the TM can
solve.


Given this fact you should be able to input the
powerset of real numbers (an undecidable problem
and halt on FA - as you don't have enough power to
proceed through the examples) by the same virtue you
do not have enough power to determine the TM-reg

 

i know this as I can recognize languages w/ TM that I
cannot with DFA/ reg ie i cannot recognize
aj bk cl where j< k < l with a DFA.

 

 

 

 

 

 

 

 

 

 

 


A-CFG is a deciable language

proof by contradiction:

assumption: A-CFG is not decidable
You can use a TM to test this and
fall into many infinite combinations
ie - putting you into an issue of having
an undecidable langauge WRONG! why?
perhaps you have not thought about using
a more restricted grammar such as
chomsky (here is the benefit here... that
we were so missing in the earlier chapter)
can bring the derivations down to 2n-1 steps

 

Decidability Thoughts

A-DFA is a decidable langauge (pp 166)
what?
A-DFA is the acceptance of for DFAs of
whether a given  DFA accepts a string
to be expressed as a language.

why?
lets try prove by contradiction this time.
assume A-DFA is not decidable.
why?
present a TM that decides A-DFA.
we KNOW TM's recognize the set of langauges
that are TM-RECog or r.e. (recursively
enumerative) and we know that a language
represented in strings can certainly exist
in the r.e. category. right ? convinced?

no.- because of one key word (pp 167)
"imagine how you would write a program to
carry out a SIMULATION...(in paragraph descr
the PROOF)"


just like the HALTING problem simulates
the execution of a TM you in this case
are writing a program (ie manifested  - not
necessarily in this case but by means of
example....in a Turing Machine).

think of a robot being programmed to execute
the DFA's on paper (of course a poorly programmed
robot might not accept/ reject...but we are not
saying if you can write a crummy robot or a looping
halting machine for that matter - but if such
a 'decidable language' exists (A-DFA) meaning
that you CAN program a successful (in this case
decidable) TM that will not loop and you can because
you are strictly following the design of your
FA.

 


A-NFA (def: see book)
A-NFA is decidable - hopefully you feel good about
A-DFA. If you do then A-NFA (as we all know that
NFA and DFA support exactly the same language
since we can express one with the other and can convert
them by a specific process from NFA to a DFA.

yes - by books detail and my argument earlier (a
thousand times yes.)

NOTE: nondeterministic and deterministic grammars
do NOT have the same level of expressiveness - keep this
in mind! as we have to rely on this information in
the similar comparisons with CFG!


E-DFA (IE if a FA accepts any strings at all)
you might have a slightly harder time accepting this
after all - (unrecognizable langauges might loop to
see if they are accepted) - BUT. they don't why?
because again we are simulating FAs which don't
get caught in endless loops - by the same notion are
not that powerful either.


EQ-DFA is decidable
yes. by the same notion that the earlier ones are and
by the application of basic logical structures.

 

PCP

asks whether we can construct a sequence
given two sets of strings that when
appended give the same exact string

NOTE: some presentations as in the book
define repetitions of the strings some
don't mention - either way it is the
same problem

what specifically is the problem
looking for?

given w = {1, 0 }
given v = {01}

we can construct

0,1
01,
which
is 01==01

more complicated

given w= {01,11,00,10}
given v ={0,1,11,01}

(simplified , by baking
 in the repetition gives:

w1,w2,w3,w4
v1,v2,v3,v1,v4,v1

or
01,11,00,10
0,1,11,0,01,0


01110010 == 01110010
solved!

(hmmm. this can ramp quickly)

 

wait, lets try a simpler implementation

MOD-PCP or MPC for short(er)
says you have to take the first
from both languages to start

certainly if you solve MPC you can
solve PC (but as the book says it
is not the same the other way ...
as some problems can only be solved
by the complete PCP taking in consideration
all of the potential starting points
but we start here for brevity.

 

we solve this problem
by considering the equivalence of the
complexity of expressing an unregulated grammar.


thus we compare this problem to
the equivalent of a grammar


if we can do that then we can
consider it among our decidability
problems towards a suitable solution.

 

therefore consider a grammar

G = ({A,B,C}, {a,b,c}, S, P}
with productions

 

S -> aABb|Bbb
Bb-> C
AC -> aac.

 

and a derivation to solve
a word 'aaac'.


S=> aABb=> aAC => aaac.


we can establish the dervations
(along with our variables to
be implied derviations)
as our two sets of 'strings'


as such


 w v
1 FS=> F
2 a a
3  b  b
4 c c
5 A A
6 B B
7 C C
8 S S
9 E => aaacE
10 aABb S
11 Bbb S
12 C Bb
13 aac AC
14 => =>

 


Given the above derivation,
we can match a similar exercise as
we tried with our binary strings

        w
        1 
w1-|w10|4|.......
FS=>aABb=>aAC=>aaacE
vvv..
111
 64..

 

by following through you can
identify the correspondence with
an unrestricted grammar.

 

 

 

 

 

 

 

 

 

 

 

 

 

Big O

The design of your software has a substantial effect on efficiency thus turning what could be a very fast paced game to one that is constantly bogged down by endless waiting. The standard of measurement for an algorithm is termed as Big-O notation. The 'O' in big-O notation is the order of magnitude. It is the approximation of what a program performance requirements can be once it eventually scales up. This supports the notion that even poorly designed code can run in an acceptable time period but the true test is when extremely large data sets are applied (perhaps the most crucial points when considering gaming applications).

The best way to approximate the understanding of the Big-O notation is to use a relatively small example . We start with a very tiny piece of pseudocode.

I = 0
J = 0
Print i
Print j;

The code here would be identified as having O(1). You might be tempted to identify it as O(4) but remember that we are dealing with approximating code and at the end of the day we are not interested in what happens at the bottom end of our examples but rather what occurs when things really begin to scale up.

Now consider the following pseudocode:

For I = 1 to n
 I = 0
 J = 01
 Print I
 Print j
This is defined as the order of magnitude (or Big-O) of O(N). This means that that you would have to take into consideration that the efficiency of this section of code is really determined as that of approaching 'n' . This is vastly larger than our last example due to the fact that it will vary according to the data approximated.

The next examples demonstrates an using two loops one following the other and a second as a inner loop , Here the magnitude is O  where if n were equal to 1 million the difference between the two sections is 1 million compared to 1 billion. That is where we refer to as the difference in magnitude.
// o(n)      // O
for (I = 0;I < n;i++){    for (I = 0; I < n; i++){
 //do something!     for (j = o;j < n; i++){ 
}        // do something!
For (j = 0;j < n;i++){     }
 //do something!    }
}

 

 

 

 

 

 

 

 

 

 

 

 

recursion theorem ponderings.....

 


1.living things are machines
2. living things can self-reproduce
3. machines cannot self-reproduce

 

3 is wrong!

 

the hard part here is not just the act of
duplication but rather the act of duplicating
a machine that has the ability to duplicate itself!


?

 

this points to somewhat of a circular definition
as the book plays with 'A defined in terms of B'
(pp 219)

the 'simple' solution (of course using the term
slightly loose...) is to liken it to

print out this sentance


- but 'this' implies the self-refernece capability
that you don't have in programming languages

lets play with some code to try to program our
way out of this one!

 

lets try to write a program that writes programs
that (ahem... 'writes programs'!... and you know
what those programs that THEY write do..!)

 

 

 

 


#include <stdio.h>
main(){

print (' #include<stdio.h>
         main(){
     print (   <THIS!> )
 }
 '
      )


}

 


really by trying to code you can see the
two parts
one is the means of replication
the second is the actual contents


this is represented by the


print out two copies of the following second in quotes
"print out two copies of the following second in quotes"

 

 

perhaps a suitable implementation might be

 

main
pointer *this;
*this = read_myself()
print *this

 

 

 

 

using this concept supports MIN-tm

which says M is minimal if there is no TM equivalent that is
a shorter desription.


make a copy of M call it 'C'

assume an enumerator for MIN-tm called 'E'


run 'E' until you have a language 'D'


this is the exception by which you cannot prove
everything to be minimal - ever -

due to the fact that a turing machine can exist
that duplicates itself (a self-duplicating - duplicator!)
will never produce a minimal language to itself - how
can it ? it is only producing itself nothing more
nothing less - where by contradition my proposal is wrong
making MIN-tm NOT EVEN RECOGNIZABLE!

 

 

 

 


finally!

a restriction on TM that gives you the
means to avoid endless looping....
the LBA (makes sense doesn't it ?)


A-LBA is decidable - as I can
model one wth a TM specifically
defined by the retrictive measures

 


E-LBA
is not decidable

why not?

as it is mentioned by computing histories,
it comes down to the consideration of the
strings processed through M or if I can model
a TM as an LBA I can take as input all the computing
states (intermediate strings) as input and
consdier them against their output.
With my 'tester' an E-LBA considering that
one exists (which it doesn't!)

It is not about proving this wrong  - we know it
is wrong but we are not trying to prove it
through contradition but rather through
reduction.

so consider our tester(E-LBA) takes 'B' and compares against
all of the histories telling me that if it accepts then
my language is not empty otherwise yes.

If it worked A-TM works -
A-TM does not work (ie not decidable)
therefore E-LBA is not decidable.


what was the bridge between E-lba (and the
difference bewteen E-LBA AND A-LBA ) once again
is the fact that i dont' know the language I am testing
against (or rather i need to pull from r.e. language
to test 'B' with E-LBA which by the way does not exist...)

 

 

 

 

 

 


GRAMMARS


CF, UNRESTRICTED

 

back to chapter 2.3 we were
presented wtih context free
grammars

what was the context-free part?

we know about cf-pl meaning that
there are languages that are out
of the expressiveness of cf-grammars
but NOT out of the expressiveness
of unstrestricted grammars.

what is the difference?


unrestricted grammars allow multiple
variables on the left-hand side of the
rule expression


ie


S-> Ab | Bc
Ab -> d

 

where in cf-grammar the 'Ab'  in Ab -> d
is not allowed.


How is this relevant?

 

by utilizing unrestricted grammars one
can feel better about our earlier
statements
 that ALL-cfg and E-cfg are undecidable


as unrestricted grammars can be used to
express all r.e. languages - this should make
you feel better about the computation
 histories-based proofs in support of
our ALL-cfg and E-cfg.

 

how can we demonstrate that the unrestricted
grammars represent the same set of A-TM ?
(r.e. langauges?)


you can consruct an unrestricted grammar
from a TM

 


example:

let M = (Q,S,T,Q,B,F) be a machine
(('B' is my little box marker))
(('S' is my summation))


transition_funct(qo,0) = (qo, 0, R)
transition_funct(q0,B) = (q1, B, L)

S->BS | SB | #A
A -> 0A | 1A | A0 | q1

 

0qo - > qo0
q10B -> 0 qo B
q1 1 B -> 1 q0 B
q B B -> B qo B


#q0 ->  lambda
B -> lambda

 

<cover rest in class>

 

 

 

 

L = { an bn cn: n >= 1}


(not cf (( of course not by cf-pl , since you are the master... ) ) )


but an unrestricted grammar....


S -> abc | aBbc,
Ab -> bA,
Ac -> Bbcc,
bB -> Bb
aB-> aa | aaA.


done (we will derive in class!)

 

 

 

 

 

final thoughts!

 

regarding Chomsky hierarchy and decidability:

notice the theme here?


emptiness is always a little harder to support as
you don't know the language until you you know the
language (?). meaning you might have to delve
beyond the capablitiy of expressiveness of a language
to draw the line as to what fits and what doesn't.

 


since  you cannot prove (reg, CF) by using themselves
you have to expand into TM constructs (or unrestricted
grammars) to explore r.e. languages - this
always takes you into the realm of undecidability


because of TM being r.e. ( ref. prior notes and book!)

 

ALL-CFG , EQ-CFG .....
are undecidable predicated on the fact that
(what we know about r.e. and turning machines!)
pp 197 - that CF-grammars produce all possible strings


they don't by (rerfence my unrestricited grammars notes!)
the fact that you can demonstrate grammars for every
turing machine (albeit unrestricted) by this virtue
alone will make you feel better about the twists and
turns of examination by computng histories -

*  THOSE HISTORIES DELVE INTO r.e. languages


* r.e. languages are beyong reach of CF-grammars (cf-pl!)


-'gr' labs team!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MIN-tM AND THE AMAZING RECURSION MACHINE

STEP 1:
UNDERSTAND THE RECURSION THEOREM.
(check my notes - hope they help.)

STEP 2:

MIN-TM is a minimal representation of its
language.


(that is our definition of MIN-TM)

we prove it to be unrecognizable by using
example of the recursion theorem.


by this we mean that we use the example of
a minimal represetnation of a machine whose
language it generates .....
are self duplicating machines which generate
machines that are self duplicating

(someone told me that the machines it generates
also generate machines that generate machines ,
which in turn generate machines....
kind of like looking a a reflection of yourself
in the mirror holding up a mirror of your
reflection)

or perhaps (simply?) represented or articulated
by the following


print two lines the second of which is in quotes
"print two lines the second of which is in quotes"

 

 

 

 


seriously here - we are really demonstrating this
by bridging the terms of machine and langauge - that
is really the essaence of our proof.


as in using contradiction.... we assume MIN-TM
exists


assuming it does ... we can enumerate the language
it produces - interestingly the language this machine
reproproduces are MACHINES!

(dont dwell too much on the self-duplicating.....)

 

(think nice thoughts like our enumerators we knew when
were younger like for the langage a (to 2 to the nth power)
such as aa, aaaa, aaaaaaaa ,...


except that our words of our language are machines
some having greater repreestnations than others
as we need a machine that produces machines
(and they do exist ... ask anyone who writes viruses for
a living)
to demonstate our paradox here.....


therefore .... moving right along....


E is our 'enumerator' for MIN-TM

Running 'E' generates the langauge of machines.


MIN-TM produces 'C'


eventually 'E' will produce a larger representation of
of 'C' as 'C' is mnimal.


'E' produces 'D' (the larger represetnation)


problem.
'D' is never larger than 'C' they are always equal
as 'C' cannot be larger than itself or what produced
it since it is by its very essence a self duplicating
duplicator
!

 

case closed.
-gr - team.






 
MIN-tM AND THE AMAZING RECURSION MACHINE

 

MIN-TM is a minimal representation of its
language.
(that is our definition of MIN-TM)

we prove it to be unrecognizable by using
example of the recursion theorem.


by this we mean that we use the example of
a minimal represetnation of a machine whose
language it generates .....
are self duplicating machines which generate
machines that are self duplicating

(someone told me that the machines it generates
also generate machines that generate machines ,
which in turn generate machines....
kind of like looking a a reflection of yourself
in the mirror holding up a mirror of your
reflection)

or perhaps (simply?) represented or articulated
by the following


print two lines the second of which is in quotes
"print two lines the second of which is in quotes"

 


seriously here - we are really demonstrating this
by bridging the terms of machine and langauge - that
is really the essaence of our proof.


as in using contradiction.... we assume MIN-TM
exists


assuming it does ... we can enumerate the language
it produces - interestingly the language this machine
reproproduces are MACHINES!

(dont dwell too much on the self-duplicating.....)

 

(think nice thoughts like our enumerators we knew when
were younger like for the langage a (to 2 to the nth power)
such as aa, aaaa, aaaaaaaa ,...


except that our words of our language are machines
some having greater repreestnations than others
as we need a machine that produces machines
(and they do exist ... ask anyone who writes viruses for
a living)
to demonstate our paradox here.....


therefore .... moving right along....


E is our 'enumerator' for MIN-TM

Running 'E' generates the langauge of machines.


MIN-TM produces 'C'


eventually 'E' will produce a larger representation of
of 'C' as 'C' is mnimal.


'E' produces 'D' (the larger represetnation)


problem.
'D' is never larger than 'C' they are always equal
as 'C' cannot be larger than itself or what produced
it since it is by its very essence a self duplicating
duplicator
!

 

case closed.

 

-'gr' team.