- Colloquium
- Amanda Tucker, University of Rochester
- “Multiple Zeta Values”
- Thursday April 7th, 4:00 pm
- Newton 204
- Usual extra credit for write-ups
- “Reductions via Computation Histories” in section 5.1
- Definition of computation history
- Sequence of configurations leading to accept or reject
- Non-halting Turing machine doesn’t have either kind of computation history
- Linear bounded automaton = Turing machine that doesn’t move head past input
- Acceptance decidable for LBAs
- Emptiness not decidable for LBAs
- ALLCFG undecidable
- ALLCFG = does a CFG generate Σ*?
- Change problem to does a PDA accept Σ*? (ALLPDA)
- Reduce ATM w/ inputs M and w to ALLPDA via computation
histories
- Design PDA to accept accepting computation history for M on w?
- Problem lies in checking whole series of configurations
- … # ci # ci+1 # ci+2 # … looks unrecognizable by PDA via similar pumping argument to … # u # u # u # …
- Design PDA P to accept all strings that aren’t accepting
computation histories for M on w
- Nondeterministically choose what criterion for being an accepting computation history is violated
- Proper starting and ending configurations are checkable by finite state machines
- Sequence of configurations: nondeterministically pick a pair #ci#ci+1# where ci+1 doesn’t match ci
- Configurations alternate being in forward and reverse order to allow this match-checking with stack
- L(P) = Σ* - {one accepting history} if M accepts w
- L(P) = Σ* if M does not accept w
- Design PDA to accept accepting computation history for M on w?
- Definition of computation history
- The Post Correspondence Problem
- Read section 5.2