Definition: An Afterlife Seeing Turing Machine (ASTM) is a deterministic machine
M = (Q, 90, 4acc, Arej; 9seer, Ayes, Ano, E, I, 8) that works like an ordinary Turing Machine with the following
Change 1. Accept and reject states are still halting states (i.e. M halts upon reaching qacc or Grei).
Nevertheless, the machine still has transitions defined by the transition function outgoing from the
Copyright By PowCoder代写 加微信 powcoder
accept and reject states. We think of M metaphorically “dying” when it halts.
Change 2. We define the afterlife of our machine to be the execution of the machine if it were to continue
working after it enters acc Or Grej. Note that if a machine enters a halting state in its afterlife, we
say it experiences a second death.
Change 3. There is an additional seer state seer that the machine can enter during its normal
before it enters any halting state. The seer state tells M whether M would experience a second
death in the afterlife. That is, the state seer transitions to the state ques iff M will experience a
second death, and it transitions to the state no if M will not experience a second death.
If seer is unable to output a logically consistent answer with the behavior of M running on 2, then
we say M explodes on input x.
Remark: Note that an Afterlife Seeing Turing Machine M is deterministic (like ordinary Turing Ma-
chines) so seer’s answer is the same regardless of when M visits seer in M’s execution.
a) (10 points) Prove that there exists an ASTM M that explodes on some input 2.
Since we don’t like machines that explode sometimes, we consider now a more laid-back machine:
Definition: We define a Best-Effort Afterlife Seeing Turing Machine (BASTM)
M = (Q, 90, 9acc, Prej, Ascer, Ayes, Ano, Amaybe, E, I, 8)
as an Afterlife Seeing Turing Machine with the following change:
Change 3′. If seer is unable to output a logically consistent answer with the afterlife behavior of M, then
9seer transitions to the maybe state rather than causing M to explode. However it can only transition
to @maybe if transitioning to yes Or 9no would have caused an ordinary ASTM to explode.
b) (20 points) Prove that there exists a BASTM M that decides the language EMPTY = ((N) : L(N) = 0}.
For all parts, remember to first write your intuition before writing your formal solution.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com