compsci3

compsci3

Fri 11/07/08

Let L be an infinite context-free language

Then there exists integer M >0 such that any w in L , |w| ≥ m, can be decomposed as w = uvxyz with |vxy|≤ m and |vy| ≥1 and uvixyz in L for all i = 0 , 1, 2, ...

"proof" .. m is related to |V| .. the number of variables in the graamar

from S ==>* uAz

and u, z can be empty .. but we reach some variable A where

A=>* uvAyz

so A in some number of steps can produce vAy .. ciclic .. come back to my self .. and critical |vy| ≥` .. so we add some characters .. a least one

.. talking terminals here .. not variables

==>* uvxyz

.. so A=>* x

given that my language that is infinite, there must be a variable that loops to itself and produces something .. and it terminates

reachable from S, terminates, and it loops to itself in souch a way that it produces a character before it loops back to itself.

S ==>* uAz ==>* uxz

or

S ==>* uAz ==>* uvAyz ==>* uvxyz

but also as many times as I want

so we know if we have an infinite context free language, that this has to be.

that is the gist of thh proof .. m .. comes from the number of variables

so an example:

L1 = {w#w| w in {a,b}*}

o it's a string concatinated with itself and useing the # to make it easier

show L1 is not context free.

as before, assume L1 is context free .. we know that L1 is infinite , since w is from Σ*, which is infinite

apply the pumping lemma

m>0 is given

so all of this is familiar

choose w = a^mb^m#a^mb^m

remeber that the length of vxy is ≤ m .. and that can happen anywhere along the string .. unllike regular languages .. doesn't have to start from beginning

|w| = 4m+1, which is clearly bigger than m

but we have numerous cases

I can choose vxy out of the first set

case 1.

vy = a^k .. comes out of the first set of a's, 1≤k≤m

case 2 .. vy = a^k1 b^k2, k1, k2≥1

1≤ k1 + k2 ≤m

choose themm to be bigger than or equal to 1 becuase otherwise we fall back to case 1

case 3 vy = b^n ....

case 4 vxy = b^k1#a^k2

four more cases .. all a's ab's and just b's .. actually that's three

so that makes this all quite ugly .. have to disprove each one

for case 1 = i=0

a^m-kb^m#a^mb^m

and that's not the same

can also use i=0 for case 2 .. .. that's tnot the same either .. i don't have ans many a's as I aave a's

i=0 also works for case 3

a^mb^m-k # a^mb^m .. no longer equal

sono matter what, I Have to ifnd a way of showing that they're not all the same

and we picked the string we did because of case 4

now if we chose 0

a^m b^m-k1 # a^ ....

and that will generate not the same

vy could just be the # symbol.

then I end up with i=0 will also fail

a^mb^m a^mb^m, which is not in my language because I don't have the #

suppose we had used a^m#a6M .. that's in the language

but we don't always have a contradiction.

so the choice is reaaly important

author language

L2 = a^nb^j | n=j^2

ab in lang .. 1=1^2

a^4b^2

a^9b^3

Show L2 is not cfl.

and this is a strange one becaase we've done all kinds of stuff with a^nb^n is .. and most of the time to show something is not cf we went to one moreecharacgger

.. every b has a different number of a's associated with it .. makes it an interesting problem

L2 is infinite .. assume context free.

apply pumping lemma m> 0 given

choose w a^m2b^m

aaa ..... abb .... b

length ..

some # of a's

a's and b's

and just b's

so just 3 cases

case 1

vy = a^k

1 ≤ k ≤m

i=0 a^m^2 -k b^m is not in L, since M^2 - k ≠ m^2 -- k ≥1

case 3.

vy = b^k 1 ≤ k ≤m

i=0

a^m^2 b^m-k is not in l becaase m^2 != (m-k)^2

case 2.

vxy = a^k1 b^k2

.. when there's a split, then you can show the middle x... but you on't have to

v = a^k1b^k3

y = b^k4

.. that's possible

that would be one subcase

v = a^k2, y = a^k3b^k4

v = a^k3, y= b^k4

i=0

a^m^2-k1 b^m-k3-k4

below

a^m^2-k3-k4 b^m-k2

last case

m^2

a^m^2 -k3 b^m-k4

suppose i=2 in the first subcase. .. well then I can get some b'2 before a's .. so patterns gone.

next case again i=2, the pattern changes

so most of the time, we just ignore those .. don't have to deal with that.

so now all we want to do is what if v is some number of a's and y is some number of b'2

show that for k3, at least 1 and k4 at least 1 n < m > k

show that

m^2-k3 ≠ (m-k4)^2

(m-k4)^2 ≤ (m-1)^2 since k4 ≥1

= m^2 -2m +1

face!!!!!!! not foil!!

< m^2 -k3

1≤k3≤m

2m is clearly bigger than k3

but also 'cuz k3 is < m .. I can add the extra 1.

k3 < m

m^2-2m+1 = m^2 -m -m +1 ≤ m^2 - k3 - m + 1

k3 < m

-m+1 is negative .. m is at least 1

-m+1 ≥ 0

m^2 -2m +1 < m^2 -k3

.. since ≠, not in L

Turing Machine as Transducer

Def. a function f is Turing computable if there is a Turing maching M = (Q, Σ, Γ, δ, q0, [], F)

q0 w |--* qf f(w)

in other words, input of w, the turing machine leaves output f(w) on the tape.

.. we dont care about stuff in front of it.

cursor must be landed at the beginning of the output

our first example:

input - unary #'s ... 111 = 3 (base 1)

f(x) = {1 if x is odd, 0 x is even}

plan - traverse the input using states for even and odd

when I encounter [], write a 0 or 1 and move left.

see attached.

f(w) = # of a's in input (unary)

plan: go left to right

on a , run right .. do blank, make it a 1

run left to blank.

repeat until you hit a 1

always get to assume we don't hav empty string

part of the tape as input and part of it as output

.. but we have as much tape as we want

f(w) = w#w, w in {a,b}*

so this is not a cfl

qo aab ==> aab#aab

so first goal

is to just put the marker there

and then once I see this guy .. i need to write one of those guys over there.

but I don't want to get stuck writing the same guy several times.

so we need to

q1Aab#a

|--* q1 AAb # aa

|-- q1aab#aab

see attached

preprocessor .. puts a # there.

busy beaver problem: . strange idea ...

one of those links has it

idea is to use as many cells on the tape as possible using those five states before it will terminate

some proofs hav been made about the max #

all about start with a blank tape, maximum number of states, .. how many cells can you visit and terminate.

-------

Mon 11/10/08

Def. A tM

.. deta takes a state and a tape symbol and changes it into a state, tape and left or right

partial function .. if defined, uniquely defined.

.. so it has one move

acceptor - Let m be a turing maching

L(M) = all w in Σ+ .. q0 w |---* ... qf in F

transducer

function f with domain D is Turing computable .. or just computable

if there exists a during machine TM

for a w in D

q0 w |--* qf f(w), qf in F

in this definition, the only thing left on the tape is f(w)

.. but she's OK with us not deleting.

9.2

- turing machines can be "combined" to perform more complex tasks.

we wrote M that given x it produces x+1

in fact, we can have a turing machine M st x as input gives me some x+c as output, where C is a constant.

.. just write C 1's

can write a turing machine that compares .. yes 1 no writes 0

so what about

f(x,y) { 0 x< y

x-y else

so this is kinda a combination of turing machines that we already know about

f(x) = x(x+1)

give input x .. has to do two things .. copy x, add 1 to copy and take the two and trhow it into multipler and I get the result

we've written a turing machine that copies

and written one that adds 1

need to write a turing machine that multiplies

string together TMs that do simple tasks to produce a mchine that does a more complex task .. that's how we write programs!

muliplier:

f(x,y) = x*u

x,y unary and greater than 0

input 11111 # 1111111

x of the first group, #, y of the second group

4*3 is the same as addition

so if my input says 1111#111

I want to pooduce a set of three four times

intermediate step - 1111#111# ___ <-- output

gotta copy four times

after some number of steps

111#111#111

11#111#111111

doing the same operations .. subtracting and copying ..

when we copy the three, we temporary change it to x's .. and then just change it bakk on the way back

see attached.

one that doesn't involve adding!

L = {w = w1w2 | |w1| = |w2|, w1 ≠w2}

Find the middle!

aabababbbabbab

a -> X, on left

b _> Y

a -> A, on right

b -> B

coutning off outside edges but remembering the character that was already there.

now we determine if good

continue as long as they agree

for very x, need a for every y need a b .. and quit when they don't line up

so find the middle

mark a's and b's on left differently than on right

2 . match / compare

9.3 Turing's thesis

- any computation that can be carried out by mechanical means can be computed on a turing machine

thesis .. really a conjecture .. kinda considered "not provable" .. hasn't been disproved.

.. what are "Mechanical means"?

.. if you define it as only what you currently have, then it dies for the future.

other models have been proposed that don't seem more powerful

.. don't expect to prove it, we just sorta believe it.

why?

- no other proposed model of computation is more powerful .. some are equally powerful

- any digital computer performs the same tasks .. can't do more with a current machine

- no one has suggested a problem or shown a problem who's solution can be determined by mechanical means that is not solvable on a turing machine.

what this means

definition: an algorithm for a function f : D→R

IS a turing machine TM which when given any thing from the domain eventually haults with the currect answer f(d) on it's tape

there is an algorithm such that ...

there is no algorithm st ....

and that means there is or isn't a turing machine.

so we're equating the idea of an alg with a TM

.. has to handle all input correctly, must always terminate

if it can be done, it can be done with a TM

.. we know we have a finite sequence of unabiguous steps that solves the problem.

for all input in the domain.

chapter 10 - other models of turing machines

so far, we've been using the standard TM - a two-way infinite tape, δ: QXΓ → Qx Γ x {L,R}

more models that seem more powerful

Def.

Two automata (model of computation) are equivalent if they accept the same language

two classes of automata, C1 and C2 are equivalent if:

- 1. for every m1 in c1 there exists m2 in c2 where L(m1) = l(m2)

... c2 is at least as powerful as c1

- 2.for every m2 in c2 there exists m1 in c1 where L(m2) = l(m1)

c1 = class of all DFA's over Σ = {a,b}

and c2 = class of all NFA's over Σ = {a,b}

.. c1 and c2 are equivalent.

proof:

let M1 be a DFA. construct M2 NFA st L(m1) = l(m2)

δ1(qi,a) = qj then δ2(qi, a) = {qj}

let m2 be an nfa - construct m1 DFA st l(m1) = l(m2) .. and we did this contrsction also

.. we have an algorithm for this from chapter 2.

c1 = class of DFA's over Σ= {a,b}

c2 = class of NPDA's over Σ = {a,b}

c2 is at least as powerful as c1

if M1 is a dfa, I can construct m2 npda so that if δ1(qi,a) = qj then δ2(qi,a,z) = (qj,z) .. don't touch the stack

so for every dfa , I have an npda

but I can't do the opposite because I know a^nb^n can be done by an npda but not by a dfa

so c1 and c2 are not equivalente becuase I have something I can do with one and not the other.

our first non-standard tm.

TM w/ stay put option

M = (Q, Σ, Γ, δ, q0, [], F)

Q, Σ, Γ, q0, [], F just as before

δ : Q x Γ → Q x Γ x {L, R, SZ} .. where S says stay put.

theorum - the classes of standard turing machines and stay put turing machines are equivalent

.. of course it doesn't add more power

proof -

- Let M1 be a standard TM, then M1 is a stayout TM .. I just don't have any S moves.

so stayput is at least as pwoerful as standard.

- Let m2 be a stayput TM. Create M1, a standard TM st L(m1) = l(m2)

Idea - in M2, if current config says

xqαay

and δ(q,α) = (p, β, S)

|-- xpβay

In m1 .. xqαay in M1

xβp[s]ay

p[s] is a state not in Q of M2

do nothing but read what's there and backup

|-- xpβay

m1 = (Q u {a few more}, Σ. Γ, δ2, q0, [], F)

so everything is the same except for δ and Q

where

if δ1(q, α) = (p, β, {l,r})

then

δ2(q, α) = (p, β, {l,r})

then if δ1(q, α) = p, β, s

then in δ2(q, α) = p[s], β, R

.. δ2(p[s], γ) = p, γ, L, for all γ in Γ

so for every state that we wneter with an S move, we intrduce another state -- so I can get back to where the state we were at.

-------

Wed 11/12/08

Last time:

- started chapter 10

- variants of the standard TM

- classes of automata to be equivalent

in the middle of proving:

class of standard turing machines (c1) is equivalent to the class of stay put turing machines (c2)

Proof:

Let M1 in C1 .. M1 is a standard turing machine

m1 is also in C2 without modification . just becaase I don't use the tay put option, doesn't mean it's not in there.

"c2 is at least as powerful as c1"

Let m2 in c2 Construct standard TM m1 st L(m1) = L(m2)

so, if δ2(q, α) = (p, β, {L,r}) then δ1(q, α) - (p, β, {L,R}) so it matches

if in m2 the thing stays put.

if δ(q, α) = (p1, β, S)

.. then intruduce a new state P[s]

δ1(q, α) = (p[s], β, R)

δ1(ps, x) = (p, x, L) for all x in Γ

so i'm not allowed in M1 to stay put

so if in m2 ...

so we end up in exactly the same place

must show L(m1) = l(m2)

but w3e've actuallly ccone the same kind of proof twice before

Let w in L(m2)

if q0 w |--* x q1, αy |--- x qi βy (haven't moved

if this is the first time i used a stay put rule,

then q0 w |--* m1 xq1αy |--> xβq1s |--- x qj βy

replace all other occurances similiarly

therefore, w in L(m1) 'cuz i'll get to the end

q0 w |--* x qf y

new variant

TM with multiple tracks

1 Tape with n tracks

still have control unit

.. one read /write cursor but multiple tracks

"using 3 bits per char"

.. represents essentially one input

but we can treat that as a one tape machine

where in order to do anything, i have to know the next three characters .. but that's not too bad

one read write head

d(q, [a, b, c] ) -> (p1 [ x, y, z], L)

so we deal with all three tracks at once

.. but if we have n symbols on a 3 track, we have n^3 on the single tape

but we can do that

theorum .. class of std turing machines c1 is equivalent to multitrack turing machines (c2)

Proof much like before

m1 in C1 .. construct m2 in c2 from δ1 st

δ1(q,α) = p, β, L/R

q, {α, z, z) = p, y1, y2, y3 , L/R

xi in Γ

so I can easily make a multitrack out of a one track .. just dont pay attention to the others

so c2 is at least as powerful as c1

Let m2 in c2

construct m1 in c1

Γ2 is of size n

let Γ1 = n^t, where t = number of tracks

and then ajust δ

if δ2(q, [x, y, z}) = (p, a, b, c, } l/r

then

δ(q, []) = q, [] / L/R)

.. each possible triple is mapped to a single character.

so not exciting but doable

.. so by giving myself extra memory, i haven't given myself any more power.

why bother?

Theorum - class of standar TM's (c1) is equivalent to the class of TM's with one way infinite tape (c2)

.. seems like it's a step backwards ..

C2

__________________

[ | |

------------------

^

if we're only allowed one tape .. let's ask for another track

c2^ .. 1-way infinite 2-track

so we treat the bottom as the left side .. we have essentially two sets of states .. am i paying attention to the top or the bottom?

.. and we switch our lefts and rights

but if we have a two way infinite tape, I can fold it upon itself at the end and have a one tape two track .. but we just said that a two trakc is equivalent to a single tape

.. so it all works.

10.2

TM with multitapes

[control unit]

with as many tapes as I want .. for each tape I have a cursor

δ: Q x Γ^n -> Q x Γ^n x {L, r}^n

δ(q, b, a, i) -> ( p, a, e, k , L, R, L)

makes f(w) = ww very easy

they're very nice

more power? no.

.. clearly we can convert a standard to a multitape .. just ignore the other tapes

going the other way

.. could model each part on a separate part of the tape

3 tapes -> 1 tape, 6 track

and then we know that we can take a multitrack into a single tape single track.

author solution : use one ttrack for old tape .. use another track to use 1's and zero's to keep track of cursor

but then you gotta find the one on each track each time and make the appropriate adjustment

so we don't get any more power .. we do lose a ton of efficiency

def.

- a non-deterministic TM M(Q, Σ, Γ, δ, q0, [], F)

Q, Σ, Γ, q0, [], F

as for standard

δ: Q x Γ --> 2^(Q x Γ x {L,R})

δ(q, a) = {(p,b,R), (q,b, L), (r, c, L) }

or

δ(q, a) = empty

now technically our δ is a total funciion .. we just definined it for everything.

DFA to NFA .. equivalent

PDA's NPDA's .. not equivalent

TM, NDTM

non-determinism .. doesn't seem very mechanical

.. we can do a recursive simulation

.. they are , indeed , equivalent

adding non-determinism can increase efficiency

any turing machine m1 can be converted to a non-deterministic TM M2

δ1(q, a) = (p, b, L/R)

δ2( q, a) = {(p, b, L/R)}

δ1(q, a) is undef.

δ2(q, a) is empty set.

so that way is easy

other way is harder of corse

m2 is a NDTM, construct M1

Idea:

m1 behaves as m2 until a choice must be made

compute all possible moves but separated on the tape.

b a b b

^ql

in m2

δ(q, a) = {(q1, b, L), (q2, a, R)}

what happens if I apply first poss.

b b b b

^q1

b a b b

^ q2

store both of those

x q1 b b b b + b a q2 b b x

.. so stack frames.

so I can do it.

author does a nice job with the description

-------

Fri 11/14/08

- turing's thesis

- anytihng that can be computed can be computed on a TM

- algorithm as TM

TM is as capable as today's digital computer

so far, each TM performed 1 alg

today's digital computer has all these programs

but also as input, we can send a program that it can perform

we're allowed ot program a computer to do different things .. right now, our TMs are single purpose.

we have all these little machines but each of them do one thing

10.4 will solve that

The universal TM

.. programmable TM that can simulate other TMs

M[u] is the universal TM

. a three tape TM

program, input/output, and simulator - internal state of a simulated TM

fetch, decode, and execute.

so the universal TM is our digital computer

Turing Machine M[u] takes as input

<M, w>

M is a description of a TMw is my input

.. simulates M on w

encode a TM M

M = (Q, Σ, Γ, δ, q0, [], F)

(q0) -- a, b, R ---> q1

δ(qi, aj) = (qk, am, L/R)

δ(q2, a3) = (q4, a5, L)

011011101111011111010

so we have to say that q0 is really q1 .. and the final state is typically q2 .. but that's just a convention

Γ = {a1,a2, .. an}

so not hard .. just boring.

every rule has 5 parts - 5-tuples

verification

.. does it break up into strings with 5 parts

does the first part show up again -- deterministic or not

1. How many TM's are there? - countable

2. How many Languages are there?

Definition of countable:

A set is countable if its members can be placed in one-to-one correspondance with the positive integers.

Positive integers Z+ = {1,2 , 3 ... }

S = {a, b, c}

1, 2, 3

countable but finite

S = {0, 1,2,3, . . }

1 2 3 4 ....

the n-th one is n-1

Z = { -3, -2, -1, 0, 1}

Z+ {1,2,3,4 ..}

0, 1, -1, 2, -2 ...

n --> 0 if n=1

n/2 if n is even

-(n-1)/2 if n is odd

a finite set is countable

all integers is countable

how many 1 x 1 squares in Quadrant 1?

do it diagonally .. eventually get to everyone

"anything infinite will you take a little while"

.. so countably infinite.

answer to the 2nd quuuuuuuuuuestion : uncountably infinite

the number of strings in Σ* where Σ={0,1} is countable.

.. we did this in lab 2!

0 1 001

1 2 3

a set is countable iff there exists a method by which all elements in a set can be written in some sequence.

ie, can be enumerated / listed .. etc

enumerable is a synonym for countable

enumerator is a TM that lists the elementes of a set

.. if i'm looking for a particular string, I stop when I get there

start with nothing on the tape .. and aftersome number of sets, I have some string s[1] and then I can continue on and procduce s2 .. and I can continue on where these guys are members of the set.

1. turing machines are encodable as strings of 0's and 1's

2. Σ* = {0, 1} is countably infinite

{encondings of turing machines} is subset of Σ*

the number of TMs is smaller than the number of strings, so therefore countably infinite.

HOw would I build an enumerator of Turing machines?

[enumerator for Σ*] --> x[i] .. [ verify if x[i] is teruing macine or not]

fivetuples everywhere, and no repreated prefixes

and then I've got a TM

If it is, list it / print it.

If not, I simply go back and get the next guy

so i'll never get done, but eventually I'll reach the one I want.

the first turing machine.

q1 on an a1, writes an a1 and moves left

diagonalization

- - - - - -

List all the rationals / fractions

0/1 1/1 2/1 ..

0/2 1/2 2/2 3/2

...

so we go diagonally through the list.

decimals

--------

"Proof"

suppose the reals are countable

then R1, R2, R3, ....

is a list of all reals

r1 = .r11 r12 r13 r14

r2 - r21r22r23

where r[i][j] in {0, 1, ..9}

rn = rn1 rn2 rn3 ...

.. all possible reals between 0 and 1

construct r* = r1*, r2*, r3*

where r1* ≠rjj

the jth digit of r* ≠ the jth digit of r[j]

r*1 ≠ r11

so r* ≠ r1

if this list is countable, then it's one of these guys

but then r2* ≠r22

since r* ≠ r2

so we're making somebody that's not in the list.

.. so it's not countable

r* is not in {r1, r2, r3 ..}

but it is a real .. therefore the reals aren't countable.

-------

Mon 11/17/08

exam 3 - Tuesday, Nov 25

- TM's

chapters 9 and 10 and the definitions of today

Last Time:

1. encode a turing machine as a sequence of 0's and 1's

δ(qi, qj) = (qk, qm, R)

0ii0ii0ii0ii0ii0

we know that we could parse this out if we had to

so that's the first thing

the second thing: defined countable

- a set is countable if it can be placed into 1:1 correspondance with the positive integers z+ = {1,2,3, .. }

- alternate definition: a set is countable if it's elements can be listed (enumerated) in such a way that each element is listed in a finite amount of time.

not that all of them are listed .. that each are.

so the idea is .. if this is my proper order for strings in Σ = {0,1}

0 1 00 01 10 11 000 001

if we have a stirng of length 2 .. I know huow many guys are prodced before it

so I know that if i'm looking for something of length 2 ..

we know how many we have to produce before

any string of length 3 is done in that time frame

any string of length ≤ k will occur in that time frame

(2^1 + 2^2 + 2^3 .. + 2^k)

3. showed that Σ* = {0,1}* is coutable

.. we just made the list

4. from that, {encodings of TM} is a subset of Σ* and is therefore countable

we used an enumerator procedure

Σ* enumerator .. produces xi .. then we trhew it into our TM recognizer .. if true, then write xi

if false, write nothing but then regardless, I come back and get the next guy.

Enumeration procedure .. lists all elements of a set.

at some point, it will get to each and every one.

subset of countable is coutable.

def1:

Let S be a set of strings on some alphabet Σ

then an enumeration procedure for S is a TM that can carry out the sequence of steps qo [] --> qs x1# s1

|--* x2#s2 |--*qs x2#s3

where s= {s1, s2, ..}

qs signifies membership of the string that follows the #

.. the reason x is sitting there is that we need something that says we're this far, give us the next one.

xi should be a member of Γ* - {#} (Γ-{#})*

what comes after the # is my guy

thought #1 - any regular language is countable

idea:

Σ* enumerator produces xi

(start with i=0) .. Σ* enumerator produces the next guy.

--> TM that accepts the regular language .. but we know that's not a problem .. DFA to TM is easy .. just do the states and move right

if it accepts, we write xi

if we reject, we write nothing.

and then i++

so this will list all the strings in my language

.. so any regular language is countable

.. we have an ennumeration procedure for any regular language

2. we have an ennumeration procedure for any cfl

1. enumerate xi

2. CFL --> NPDA

how to do with a TM?

two tapes .. input on one , stack on the other

could use one .. we only have to pass through the input once .. so read a guy, zap him and do what I have to do

so I can use a tm to model a stack

i++ go to 1.

TM that simulates NPDA

relies on simulation of non-deterministic TM simulation

ended last time with uncountable proof

Theorum - (not needed for this course) .. technique is important

the # of real numbers in the interval (0,1) is uncountable

proof - uses diagonalization which typically means contradiction.

Assume the reals in (0,1) are countable and that R = {r1, r2, r3, .. } is a list of all reals in (0,1)

construct r* st r* is a real in (0,1) but r* is not in the set

.. missed one! .. so #'s reals in (0,1) is not countable!

construct an r* st r* ≠r1, r* ≠r2, r*≠ r3

.. not any of 'em

construct r* so that the ith place of r* differs from the ith place of r[i]

so if r* differs from r1 in the first place, from r2 in the second place it's not r2 .. etc

r*[i] = (r[i][i] + 1) %10

ith digit of r does not equal the ith digit of r[i]

for example:

r* is not rk for any k

but he's clearly in (0,1)

so my claim that i can count them all is wrong.

if something is bigger than an uncountable , it's uncountable

Theorum

- the number of languages over Σ* (Σ={0,1}) is uncountable

If Q is countably infinite, then the size of the power set 2^Q is uncountable.

if Σ* is countably infinite, then the set of all languages (a language is a subset of Σ*) is uncountable.

there are many languages for which TM's won't recognize.

regular

context free

recursive languages

recursively enumerable languages

everyone else

TM can do regular, cf, recursive and mostly do recursively enumerable

can't do else

example of else

enumerate the TM's m1, m2, m3 ... over Σ = {a}

L = {{a^i) st ai not in L(M)}

Definition - A language L is recursive if there exists a TM M st

1. L(M) is L

2. M haults on all w from Σ+

my M does not infinite loop

if I set as input w into my TM M, it always stops and says accept or reject

TM M is a membership algorithm for L.

Definition

----------

A language L is recursively enumerable if there exists a TM M st

L(M) = L

.. does not say it will stop

will say accept for all w in L

but if w is not in my language, it might reject or it might infinite loop

so i don't always get the answer.

.. how long do I wait? you don't KNOW

.. so you can know accept but not all reject

recursive vs recursively enumerable .. it always haults for recursive.

Theorum .. the set of languages over Σ* (Σ = {0,1}) is uncountable

pwoof

assume the set of languages L is countable

so L = {l1, l2, l3, ... }

we know Σ* is countable, so Σ* = {x1, x2, x3, ... }

construct the table

x1 x2 x3 x4 ..

L1 1 1 1 0 1 0

L2 1 1 0 1 1

L3

table T[i,j] = 1 if x[j] in L[i], 0 else

all of my languages using all of my strings filling in this table.

i need to show that the L is missing

goals:

constuct L* subst Σ* st L* ≠k for any k

i'm going to make L* different from L1 by saying don't put xi in L*

construct L*:

xi in L* iff xi not in Li.

since L is countable, L* must = Lk for some k, since "the list is there"

suppose that xk is in L*

xk in L* is true iff xk not in Lk

by the definition of L*

S L ≠ Lk because they differ on xk

So xk is not in there iff xk in Lk

but xk gotta be either in it or not in it

there doesnot exist k L* = Lk

so L is not countable.

shows our definition of L* produces a language not in the list.

so there are more languages outside of our circle than are on the inside.

-------

Wed 11/19/08

Exam 2 - tuesday nov 25

chap 9, 10, 11

Last time:

---------

Def. a language L is recursive if there exists a TM M st L is accepted by M _and_ M haults on all input

Def. a language L is recursively enumerable if there exists a TM M st L(M) is L .. it haults and accepts every string in L and other than that we on;t know how it behaves

also last time:

proved that the number of languages over Σ is uncountable

proved - the number of TM is countable

"There are an uncountable number of languages that are not even RE, much less recursive, or CF, or regular

all kinds of things that we cannot do with a TM and if i cant do them with a tM, i cnnt' do them algorithmically

Theorum: for any non-empty sigma there are languages that are not RE

regular

context free

recursive

re

non-re

step 1 - we can enumerate any recursive language

if L is recursive, I should be albe to list its elements

enumerator for Σ* -- xi -->

and because my language is recursive

TM M on input xi accepts xi or rejects xi, but since my language is recursive, this always haults .. guaranteed that I have a TM that always haults no matter what input i"m given

.. so print x and go on .. and then get the next xi

so there's my enumerator.

we can enumerate any RE language but cannot do it in the same way.

if we try to say well ok that M . if that M truly does accept w if w is in the language, i will eventually write it but i might never get to that w

.. never get to ask if x5 is in our language if x4 never terminates .. M is not guarrenteed to hault on all xj .. so we don't get to xj+1

so we need another solution

step# w1 w2 w3 w4

1 1 2 4

2 3 5

3 6

.. so two steps on the first guy and one step on the 2nd

so we're parallel processing here

...

enumerator for an re language L

Let E enumerate Σ*

Let M be a TM st L = L(M)

0. i = 1

1. E gives wi

2. Run M for one step each on w1, w2, .. wi

if M haults accepts wj, list wj

3. goto 1

if I never get to stop and say accept or reject, the fact that this guy never haults doesn't stop me from being able to accept w4

how many steps?

suppose wk is accepted on its mth step

.. close to m(m+1)/2

but i'm guarrenteed to get to the mth step at some point.

** remember the idea of alternating moves

an RE language that is not recursive

regular

cf that is not regular

recursive that is not cf

and now .. show re that's not recursive and show some non-re

Theourm: there exists an re language whose compliment is not RE

create an L that sits inside RE

show that his compliment is out there

so recursive is closed under complimentation, but not re

if a language is recursive.. acepts or rejects, then I can just flip the results for the compliment .. I can do that because it always haults.

proof:

the number of TMs is countable

therefore this is a list of them all M1 .. M2 .. M3 ..... ..

is a list of all TMs in proper order

define L = a^i st a^i in L(Mi)so if the ith TM accepts the input i a's, then my language will accept it.

first claim: L is RE

ie, there exists a TM that accepts all w in L

.. don't care if it doesn't stop .. all i care about is that it does indeed accept

does the 2nd TM accept aa .. if not, aa is not in L

a^i is in L iff a^i is in L(TMi)

a aa aaa a^4 a^5

M1A R R R R

M2A R R A

so looking down the diagonal

so far, L holds a and a^5 .. so that's how I"m defining L

claim now is that L is RE

to show that L is RE .. demonstrate a TM that accepts L

TM M^ on input a^i

1. Determine i

2. Let my TM enumerator enumerate TMs until we get M[i]

3. Simulate Mi on ai

if Mi haults and accepts ai, ai is in L .. we got our answer .. then M^ accepts ai .. ie, ai is in L

so our TM needs to hault on accept and so far it does

if Mi haults and rejects ai, M^ rejects (ie ai not in L)

if Mi doesn't hault, we don't care!

.. so we just had to show a TM that accepts all L for RE .. and we did

So M^ counts i .. finite .. will always hault

2 will always hault

will 3 hault .. if it does and accepts then I know that the string is in my language

so at this point I've demonstrated that L is in RE because our TM accepts every string in our language

claim

L-bar = {ai | ai not in L(M)}

so this is my compliment

is NOT RE

Suppose L-bar _is_ RE

Then there exista a TM that accepts L-bar and since M1 m2 .. is a list of all TMs

L-bar = L(Mk) for some k

so Mk is the guy

Suppose a^k is in L-bar (this is the same K) .. my TM that accepts L-bar is the kth TM and now i"m looking at the kth string and it's either in there or its not

suppose that it's in there

ak in L-bar iff ak in L(Mk) since L(Mk) = L-bar

ak in L-bar iff ak is not in L(Mk) by definition of L and L-bar

contradiction

--><--- ak in L(Mk) iff ak not in L(Mk)

--------

so suppose ak is not in L-bar

ak is not in L-bar iff ak is not in L(Mk) since L(Mk) = L-bar

but ak not in L-bar means that ak is in L .. iff ak in L(Mk)

--><---

ak not in l(Mk) iff ak in L(Mk)

Therefore, L-bar is not RE!

really was a proof by diagonalization

Σ = {a}

L = {a^i | a^i in L(Mi)}

L-bar {a^i | a^i not in L(Mi)}

M1, m2, m3 ... is a listing of all TMs

-----

Theorum

1. L is recursive iff L-bar is recursive

2. L and L-bar RE iff L (and L-bar) is recursive

Proof of i .. L is recursive iff L-bar is recursive

L is recursive means there exists a TM M st L(M) == L and M haults on all input

Using M, construct M^ st L(M^) = L-bar and M^ haults on all input

M and M^ TMs

send w in Let M run .. M always haults becuase my language is recursive

if it says accept great or reject great .. it'll tell me one of those two

if in final state, say no .. otherwise, say yes

so if I end up in qf in M , then I make one more step and go to q[no!] for M^

this proves that L-bar is recursive

since M^ always haults because M always haults and M^ rejecdts w iff M accepts w, therefore L(M^) = L(M)-bar = L-bar

so proved ==>

now <== .. similar

.. same idea

M^ on input w runs M on w

if M accepts, reject

else accept

(ii) L recursive ==> L, L-bar are RE

L recursive says there exists TM M st L(M) = L and M always haults!

so how do I show that L is recursively enumerable?

Clearly L is RE because the same M accepts L (L(M)=L)

Claim L-bar is also RE

demonstrate a TM that accepts the strings of L-bar

construct M^ so that on input w, M^ does:

1. acts as M on w

on hault, if M accepts w we reject, else we accept

the catch here is: M always haults

.. therefore we always get the chance for M to reject.

.. this only works because M always stops .. accepts or rejects everything

L and L-bar are RE. Show L is recursive

L, L-bar RE means TM M1 L(M1) = L but M may not hault on some input

TM M2, L(M2) = L-bar but M2 may not hault on some input

construct a TM M st L(M) is L and M haults on _all_ input.

TM M consists of TMs

1. copy

go to M1 and M2 .. going to alternate steps but they each have their own memory

if w in M1, M1 will eventually hault and say yes

if w is not in M1, we don't know .. but hhat's why we have L(M2)

so M2 accepts all the strings in the compliment of W.. so if this guy accepts, we better reject

so this shows that L is recursive .. because one of these is guarrenteed to stop

.. and we can't do this for all because not every compliment of L is RE

-------

Mon 12/01/08

Last Time:

The halting problem

given a TM M and an input w, it is not possible to decide whether or not M haults when started with w

proof was by contradiction

progbably first problem proved to be not solvable

some one has to put that first one in the hat

assume that TM H solved the halting problem

send in the descritpion of m and w into H ..

M haults on w

or q no .. for m does nt hault on W

so however this black box works, it does

from H , we create H'

took description of TM and input

sent it in, behaved just as the first guy did .. but infinite loops on yes

on q no .. H' accepts (W[M], w)

H' does not hault on W[m] w iff M haults on W

so if M haults on W, now i'm looping

if M does not hault on W, H' does

from H', we create H^

H^ takes a string, copies it to produce some ww

shove that into H' and take the results of H'

looping or we hault

H^ does not hault on w iff w haults on w

let it be a TM

so now H^ haults on W[m] .. does not hault iff

..

but H' is a turing machine

therefore w[h'] is it's encoding

H^ does not hault on w[h'] iff h^ haults on w[h^]

{ <M, w> | TM M haults on input w}

W[m] W

in this language if the TM haults on input w

.. is not recursive .. (is not decidable)

is it sure it RE?

sure! use the universal TM .. run M on w .. if haults, accept <M, w>

so this is another set that's RE but the compliment is not

L[2] = {< M, w> | M is a DFA and w in L(M)}

is L[2] recursive? yes

RE? yes

Is L[2]-bar RE? yes!

just a dfa .. we have such an algorithm .. we don't ave it in terms of a tm, but becuase we believe in turings thesis then we have a TM

{ <G, w> | G is a CFG, w in L(G)}

L[3] recursive? sure ! I have a membership algorithm .. convert to CNF and do CYK

the question is can you decide whether or not w is in L(G) .. yes!

L[4] = { <G1, G2> | G1, G2 is cfg, L(g1) = L(g2)}

L4 is not recursive

is it or is it not RE

.. cannot decide if the two languages are equal

we know that we could do do that with two dfa's

interesting consequence of the haulting problem:

very important consequence of the haulting problem

theorum -- if the haulting problem were decidable, then every RE Language would be recursive .. plug it into H :-D

Proof:

------

Assume H exists st

on input w[m]w, H decides whether or not M haults on w

Let L be an RE language .. L = some L(M1), TM M[1]

construct M2 so that on input W[m]W,

1. Run H on W[m]W .. if M does not hault on W, reject W

2. If H accepts .. ie, haults, run M on w and accept if M accepts, reject if M rejects.

so we have constructed a TM that either says Yes or No.

M2

M, W goes into H

if M does not hault, reject

otherwise, run M .. and accept or reject as M does

-------

Tue 12/02/08

given dfa and a string,

final

thursday dedc 11

more unsolvable / un decidable

and some techniques

rice's theourm

3. post correspondence problem (pcp)

- undecidable

prove that the fifth tiling problem of lab 1 is undecidable (no way of knowing)

blank tape = {w [m] | m is a TM that haults when started on a blank tape}

claim: blank tape is not recursive - not decidable .. ie, there is no tm that says whether or NOT it stops of i start it on the balnk tape

proof is by contradiction

assume decidable by TM B

B takes as input some string that represents a TM and says M haults on blank tape or it says M does not ahult on blank tape

but it doesn't loop! however it does it, it does the job

if this set is indeed recursive, then I have such a TM

We will use B to solve the haulting problem.

"of course there is no such thing as proof byy picture"

given W[m] W

going to create something that uses this black box B

B takes some M[W] .. will say that M[w] haults on blank tape

or M[w] does not hault on blank tape

if it haults on a blank tape, M haults on w

and if not, M does not hault on W

construct M[W} from M and W in such a way that this is true.

how do i describe that machine?

construct M[w] from M and W?

and i want to do this in such a way that if this machine stops on no input then M haults on W

1. write W on the tape

so that's easy enough to do .. basically, copy the input to the screen

simulate M on w

so you gave me a TM and a string, so the first thing i'm doing is writing the string to the tape and then let the TM act on the string

that's the whole thing .. this is my description of M[w]

.. so we're just generating M[w] .. which is a TM that writes w on the tape and simulates M on w.

M[w] .. if he starts on a blank tape, he'll write w on the tape and then behave as M

this magic machine B says "give me any TM and i'll tell you if it stops on a blank tape"

so then M has to stop on w.

"of course I'm cheating"

if B says this things stops, then M stops

if this thing loops, I'm looking on simulating M

so if this thing doesn't hault it's because M doesn't hault on w

if it does hault, it means that this stil ends.

so the big box is a solution to the haulting problem.

but we know that H (the solution to the haulting problem) does not exist

.. haulting problem is not dicidable

therefore B does not exist.

so Blank Tape is not decidable.

this guy is RE .. run it!

but not recursive

so it's compliment is not RE

assumed it was solvable with a magic box .. I used the magic box to solve the haulting problem .. therefore, the magic box does not exist

the hard part is being creative right before the magic box .. how to I manipulate M and W in such a way that the answer to magic gives me the answer to the haulting problem.

L = {w[m] | W[m] is a TM and L (m) is finite}

if M were a DFA, we can say if the language accepted by the machine is finite .. just look for loops!

we can do with a CFG too

but we can't do this with TMs .. this is undecidable

Proof is by contradiction, of course!

Assume L is decidable by TM F.

if you send me the descritpion of a TM into F, F magically says

L(M) is finite

or

L(M) in not finite

i oon't know hwo it works, but i'm assuming it is .. that ther''s this magical routine that does this

decidable = always haults

.. a member ship alogorithm for L

once again, we soolve the haultiing problem:

Use F to solve the haulting problem

W{m} M (ie, TM and string ) that we send into H

M haults on W or M does not hault on W

somewhere in here we use the magic box F which takes in some machine .. L(M^) finite

L(M^) not finite

and on ewill say M haults and the other that it doesn't

so box before constructs M^ from M andd W

if m haults on W, that would be give the opportunity to accept

can't accept if I can't hault

finite -> does not hault

not finite = M haults

Constrct M^ from W in the following way:

on input x:

- erase it .. that's easy

2. write W on the tape

.. somehow this has to relate to w -- i need to say "m haults on w"

3. Simulate M on W

4. if M haults, accept x

1 and 2 always finish .. 3 is the ?

so suppose m stops on W, it accepts every x

If M haults on w, m^ accepts Σ*

if M does not hault on w L(M^) = nothing!

so either accept everything or nothing

and nothing is finite

and everything is not finite

so if F has the answer, then I have the answer to the haulting problem .

but we cannot solve the haulting problem

therefore, F does not exist.

this is not RE and it's compliment is not RE

E[TM} { W[M] | M is a TM and L(M) = empty}

DFA .. can certainly anser if the language is empty .. same thing for cfg

so I can answer this for CFL and regular

but this is also undecidable for TMs

the complement is RE .. this guy is not

- enumerating X[i] and Run M on x[0], x[1] , x[i] for one step .. if any accept, acccept M.

else,

i++ and enumerate the next i

Assume E[tm] is decidable

by TM E.

takes a TM M as input

and says L(M) is empty or L(M) not empty.

Use E to solve the haulting problem

create H

.. get's a TM and a string

construct M^ from M and W

M^ goes into E and says

L(M^) empty - M does not hault on w

L(M^) is not empty - M haults on w

the same trick works in a lot of situations

Construct M^ so that on input x,

- 1 erase x, as before

- 2 write w, as before

- 3 simulate M on w

if M hault, acccept x

so as a result

L(m^) is empty iff M^ does not hoault on W

so if this magic E exists , I can decide of the TM haults.

H solves the haulting problem

we know this is not so .. therefore E does not exist

One more:

EQ[TM] { < W[m], w[n]>, | m, n and tm's and they accept aexaclty the same language}

this is undecidable.

not RE nor is its compliment.

Assume that it is decidable .. recursive.

So there exists a TM Q

so that L(Q) = EQtm

Q takes in two TMs and says that L(M) = L(N)

or it says L(M) != L(n)

and always haults

can use Q to solve any unsolvable

use Q to solve E[TM] ie, decide whether or not L(M0 is empty for a TM M

E tm gets 1 tm

says it it's empty or not

and I want to use my magic Q and it gets two TMs .. M and N

L(M) = L(N) - L(M) is empty

L(M) ≠ L(N) - L(M) is not

construct M and N

1. M is the TM M

2. N is a TM that on input x, rejects x (w/o doing anything)

so L(N) is empty

so I have a TM that accepts nothing

if Q says they accept the same langauge then I know M acceptws nothing

if they say they're different, then M is not empty.

so magic Q does it's job ..

so this guy solves Etm, wich we know cannot

therefore, EQ[TM] is not decidable.

-------

Wed 12/03/08

lab 1 problem 6 -- undecidable problem

fill quadrant 1 with tiles .. no flip or rotate

see handout -- not being tested on this.

L{t} .. all t1, t2, t3 .. such that the tiles of T can fill quadrant 1

"i love destruction!"

-------

Fri 12/05/08

final Thursday @ 2:15

-comprehensive / big picture

need to know tat all cfgs have memberships alg

but you on't have to do a cyk .. just know it exists

comstruct:

cfg

dfa

TM

show someting is rgular using automata or regular grammar

show something is context free

recursive : need to do a TM

closure properties are helpful

recursive vs re

eliminate λ, usless .. need to know

.. need to be ablet o answer quesions like is this finite or infinite .. if I have looping useless staates i get the wrong answer

can convert an nfa to dfa .. nodon't ave to do it

no grammar to dfa

algorithmic stuff .. just need to know what we have avail

big picture

classify a language

.. explain , not prove

a^nb^n

" a stack is good neough" but not regular bcause i can't count

.. no pumpoing lemma problem

CLOSURE PROPERTY!!

Πµε

ΣτΔ