-- Practice Final Thread
Sebrianne, Gurseerat, Michael
Q9 Define computation history.
Let M be a TM and x an input string.
An accepting computation history for M on x is a sequence of configurations C1,...,Ck, where C1 is the start configuration of M on x, Ck is an accepting configuration of M, and each Ci legally follows from Ci−1 according to the rules of M.
A rejecting computation history for M is defined similarly, except that Ck is a rejecting configuration.
Prove ELBA is undecidable using a computation history argument.
The reduction is from ATM. We show if ELBA is decidable then ATM also would be decidable. Suppose R is decision procedure for ELBA. Let
L={w|w is a string of the form C1#C2⋯#Ck giving a legal accepting computation history of M on input x}.
One can show that L can be recognized by an LBA; let's call it B. Further, if L is empty, ⟨M,x⟩ is not in ATM. So if ELBA were decidable the following would be a decision procedure for ATM:
S= "On input ⟨M,x⟩, where M is a TM and x is a string:
1. Construct LBA B from M on x .
2. Run R on input ⟨B⟩.
3. If R rejects, accept; if R accepts, reject." Q.E.D.
In fact, ELBA is Turing-complete for co-r.e. for essentially the same reasons as ETM was.
(
Edited: 2020-05-11)
Sebrianne, Gurseerat, Michael
'''Q9 Define computation history.'''
Let M be a TM and x an input string.
An accepting computation history for M on x is a sequence of configurations C1,...,Ck, where C1 is the start configuration of M on x, Ck is an accepting configuration of M, and each Ci legally follows from Ci−1 according to the rules of M.
A rejecting computation history for M is defined similarly, except that Ck is a rejecting configuration.
''' Prove ELBA is undecidable using a computation history argument.'''
The reduction is from ATM. We show if ELBA is decidable then ATM also would be decidable. Suppose R is decision procedure for ELBA. Let
L={w|w is a string of the form C1#C2⋯#Ck giving a legal accepting computation history of M on input x}.
One can show that L can be recognized by an LBA; let's call it B. Further, if L is empty, ⟨M,x⟩ is not in ATM. So if ELBA were decidable the following would be a decision procedure for ATM:
S= "On input ⟨M,x⟩, where M is a TM and x is a string:
1. Construct LBA B from M on x .
2. Run R on input ⟨B⟩.
3. If R rejects, accept; if R accepts, reject." Q.E.D.
In fact, ELBA is Turing-complete for co-r.e. for essentially the same reasons as ETM was.