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..!)

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

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 !