-- Practice Final Thread

<u>'''(Gricelda and Jieni Yan)'''</u> ---- 7. Carefully define the class SPACE(f(n)) using offline Turing Machines, so that classes like SPACE(log n) are meaningful. Prove an analog of our linear speed-up theorem for space complexity classes. <br><br>When we are interested in sub-linear space classes, we will often assume the first tape is offline (read-only) and consider the squares used on the remaining tapes. Space (f(n)) is the class of languages that can be accepted by a DTM with read-only input tape. NSPACE(f(n)) is defined likewise, using non-deterministic machines. <br>'''Definition'''. We say that a language L is in TIME(f(n)) (resp. SPACE(f(n))) if it is decided by some k-tape TM in time f(n) (resp. space f(n)). <br>'''Linear Speedup Theorem''': Suppose TM M decides language L in time f(n). Then for any ε > 0, there exists TM M’ that decides L in time <u>'''εf(n) + n + 2. '''</u> <br>'''''Proof''''' : Encode K-tuple of symbols of M as single symbols of M', by increasing the alphabet of M'. Now, "compress" the input of M of language n to a new string (over the alphabet of M') of length n/k. This phase can be done in at most n+n/k+2 steps. Now, the simulation phase begins. In just 6 steps of M', we can simulate k steps of the old machine M. First, in 4 steps(L,R,R, L) M' will gather and store in its finite-state the symbols of M that can be scanned by M in at most K moves of m. With all that information, M' can compute what the tape of M would look like after k moves of M. The simulation phase at most 6*(f(n)/k) steps. By setting k = 6/ ε we get the total time of M'on inputs of size n is at most εf(n) + n + 2, as promised.

-- Practice Final Thread

((resource:Group.pdf|Resource Description for Group.pdf))

-- Practice Final Thread

Group 2: Keven Lam, Sartaj Singh ((resource:Capture.PNG|Resource Description for Capture.PNG))

-- Practice Final Thread

	Let M be a TM and x an input string.
	An accepting computation history for M on xis 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 Mis defined similarly, except that Ck is a rejecting configuration.

	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.

Q9 Group 6 : Prajesh, Tyler, Nick Computation history : Let M be a TM and x an input string. An accepting computation history for M on xis 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 Mis defined similarly, except that Ck is a rejecting configuration. ELBA is undecidable. Proof. 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⟩, whereM 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.

-- Practice Final Thread

 We construct a LBA(B) to test if L(B) is empty. L(B) is the computational history of M with w. The two possible outcomes for this language are:

Group: Johanna, Max, Sumaiyya Question 9) ELBA= {<M>: M is an LBA and L(M)= Ø} is undecidable Suppose ELBA is decidable. For the Turing Machine(M) with an input of w. Configuration history {C0,...,Cm} where each Ci is a configuration. We construct a LBA(B) to test if L(B) is empty. L(B) is the computational history of M with w. The two possible outcomes for this language are: 1. If M accepts w, the language contains one string and therefore is nonempty. 2. If M rejects w, this language is empty. So if some input x, for B to accept x, it must be some computational history of M with w. To break up x to be read, we add the delimiters “#” to the string. With the input divided into Ci’s we follow these rules to see if it can be accepted by B as a computational history of <M,w> 1. C0 is the start configuration for M on w 2. Each Ci+1 legally follows from Ci 3. C0 is an accepting configuration for M Once here we can see that C0 for M on w is the string q0w1w2 ...wn, with q0 as the start state for M on w. B will ensure the 3 rules listed are then followed by the input w, if not then w is rejected and L(B) is empty. However, if it accepts the input x, then L(B) is not empty, meaning w is accepted by M. Finally, we use a Turing Machine R to decide ELBA, and a Turing Machine S to decide ATM. R takes B is an input. We set S to the condition: If R rejects, accept; if R accepts, reject. If R accepts B, then L(B) = Ø, meaning M does not have computational history and does not accept string w. If R rejects then L(B) is nonempty and there is a computational history of <M,w> and so M accepts w, along with S. Question 10) We can think of the language having a property, and that property is ‘’correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem’’. Let this property represent ASCII. We want to prove that a Turing Machine’s language which has the property ASCII is undecidable. First show that ASCII is undecidable and thus we can use proof by contradiction, assuming that ASCII is decidable and has a Turing Machine R that decides ASCII. We then construct a Turing Machine S using R which follows: Let T0 be a machine that always rejects so L(T0) = empty and T0 ∌ ASCII. It can be possible to proceed with ASCII’ instead of ASCII if T0 ∋ ASCII. But because ASCII is nontrivial, there exists a Turing Machine where T ∋ ASCII. Proceeding with constructing a turing machine S that uses T and R we see: S = ⟨M, w⟩ Mw: On input x: Simulate M on w, if it halts - reject. If accepts, proceed to 2) Stimulate T on x, if it accepts - accept. Use the Turing Machine R to determine ⟨Mw⟩ ∋ ASCII. If yes - accept. Otherwise reject We can see that ⟨Mw⟩ ∋ ASCII iff M accepts w. Thus, since the construction of Mw from T, M and w takes a finite amount of steps. Then our S is the decider for our Turing Machine. This creates a contradiction because our property ASCII is undecidable. We can assume that ASCII is an infinite language. This is because there really is an infinite way of strings that can be accepted solutions for Mr Pollett to this problem. Using synonyms and permutations there could really be an infinite many combinations accepted by him. ASCII is a language of Turing Machine descriptions. It has to satisfy the following 2 conditions of the Rice Theorem: Condition 1) It is nontrivial because some Turing Machine have constricted length languages while others are infinite. Condition 2) It depends on the language. If there are two Turing Machines that recognize the same language, then both of the machines recognize ASCII or both do NOT recognize ASCII. Thus, the Rice Theorem also implies that the ASCII language is undecidable.

-- Practice Final Thread

((resource:practice final 7.PNG|Resource Description for practice final 7.PNG))

-- Practice Final Thread

	9. Define computation history. Prove E_LBA  is undecidable using a computation history argument.
	
	A computation history on an input string w for a Turing machine M is a sequence of configurations C_1, C_2, ..., C_k, such that C_1  is the start configuration for M on input w, C_k  is an accepting configuration for M, and each C_i  follows from C_(i−1)  according to the rules of M's transition function.
	
	We try to show E_LBA  is undecidable by first trying to show it is decidable, and observing what occurs.
	
	Let D be a decision procedure for E_LBA.
	
	Let B be a linear bounded automaton that recognizes the language L = { w | w is a string that gives a legal accepting computation history of a Turing machine M on an input string w for M and w has the form C_1#C_2...#C_k}.
	
	I claim that if we had a decision procedure for E_LBA, then we would also have a decision procedure for A_TM.
	
	This decision procedure for A_TM  would run as described below.
	
	For a Turing machine M and a string input w to that Turing machine, construct a linear bounded automaton B.
	
	Run our hypothetical decision procedure for E_LBA, D, on the linear bounded automaton just constructed from the aforementioned Turing machine M and the input string to that Turing machine w.
	
	If our hypothetical decision procedure D accepts an encoding of our linear bounded automaton <B>, that means the language of B is empty, meaning there is no accepting computation history for the input string w on the Turing machine M. If our hypothetical decision procedure D rejects an encoding of our linear bounded automaton <B>, that means L is nonempty, which in turn implies the Turing machine M terminates in an accept state on input string w.
	
	In other words, if D existed, we would have a decision procedure for A_TM ! But, we know A_TM  is undecidable. Therefore, our decision procedure for E_LBA  cannot exist, and, E_LBA  is undecidable.
	
	10. Use Rice's theorem to show that the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable.

	1. We must first show that the language in question, which in this case is descriptions of Turing machines accepting the language comprising "the same strings written in ASCII as Professor Pollett would call solutions to this problem", to which I shall henceforth refer to as L, is nontrivial, i.e., L is neither empty nor does it contain every Turing machine in existence.
	2. Then, we must show that whenever we have two Turing machines that recognize the same language, they are either both in L or neither of them are in L. If both condition one, above, and this condition are true, then Rice's theorem says L, or "the question of whether a Turing machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem", is undecidable.

9. Define computation history. Prove E_LBA is undecidable using a computation history argument. A computation history on an input string w for a Turing machine M is a sequence of configurations C_1, C_2, ..., C_k, such that C_1 is the start configuration for M on input w, C_k is an accepting configuration for M, and each C_i follows from C_(i−1) according to the rules of M's transition function. We try to show E_LBA is undecidable by first trying to show it is decidable, and observing what occurs. Let D be a decision procedure for E_LBA. Let B be a linear bounded automaton that recognizes the language L = { w | w is a string that gives a legal accepting computation history of a Turing machine M on an input string w for M and w has the form C_1#C_2...#C_k}. I claim that if we had a decision procedure for E_LBA, then we would also have a decision procedure for A_TM. This decision procedure for A_TM would run as described below. For a Turing machine M and a string input w to that Turing machine, construct a linear bounded automaton B. Run our hypothetical decision procedure for E_LBA, D, on the linear bounded automaton just constructed from the aforementioned Turing machine M and the input string to that Turing machine w. If our hypothetical decision procedure D accepts an encoding of our linear bounded automaton <B>, that means the language of B is empty, meaning there is no accepting computation history for the input string w on the Turing machine M. If our hypothetical decision procedure D rejects an encoding of our linear bounded automaton <B>, that means L is nonempty, which in turn implies the Turing machine M terminates in an accept state on input string w. In other words, if D existed, we would have a decision procedure for A_TM ! But, we know A_TM is undecidable. Therefore, our decision procedure for E_LBA cannot exist, and, E_LBA is undecidable. 10. Use Rice's theorem to show that the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable. We want to use Rice's Theorem. To use Rice's theorem, we must first show two things. 1. We must first show that the language in question, which in this case is descriptions of Turing machines accepting the language comprising "the same strings written in ASCII as Professor Pollett would call solutions to this problem", to which I shall henceforth refer to as L, is nontrivial, i.e., L is neither empty nor does it contain every Turing machine in existence. 2. Then, we must show that whenever we have two Turing machines that recognize the same language, they are either both in L or neither of them are in L. If both condition one, above, and this condition are true, then Rice's theorem says L, or "the question of whether a Turing machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem", is undecidable. We start by proving condition one, above. I make the assumption Professor Pollett wrote this question knowing there is at least one string written in ASCII that he would consider a solution to this problem. If this is true, then L is nonempty. There are definitely "strings written in ASCII" that are not solutions to this problem. Here is one: "Hello!" If I had written down the previous string as my answer to this question, I believe Professor Pollett would have marked it incorrect. I claim there exists a Turing machine that recognizes the language H = { "Hello!" }. Thus, there exists at least one Turing machine that does not accept "the same strings written in ASCII as Professor Pollett would call solutions to this problem". So, L is neither empty nor does it contain every Turing machine in existence. L is nontrivial: this satisfies the first condition required for use of Rice's theorem. We now attempt to satisfy the second condition. If two Turing machines recognize the same language, it is impossible for one to recognize the language comprising "strings written in ASCII" that "Professor Pollett would call solutions to this problem" while the other does not, and vice-versa. Thus, we satisfy the second condition required to use Rice's theorem, and can therefore use it. So, by Rice's theorem, "the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable."

-- Practice Final Thread

Group: Sumaiyya Burney, Jiajian Liu, and Zhijie Xu Q9 '''Define computation history''' Let M be a TM and x an input string. A computation history for M on x is a sequence of configurations C1,...,Ck, where C1 is the start configuration of M on x and each Ci legally follows from Ci−1 according to the rules of M. If Ck is accepting, the sequence is an accepting computation history; if Ck is rejecting, the sequence is a rejecting computation history. '''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.

-- Practice Final Thread

Group: Edgar Velazquez, Michael Kang, Sandeep Isher '''Problem 10''' Use Rice's theorem to show that the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable. We need to let the property “the same strings written in ASCII as Professor Pollett would call solutions to this problem” represent ASCII and we want to prove that there is a touring machine’s language with ASCII property is undecidable. First, we need to prove that that there is a language L that is not empty nor contains every Turing machine there exists. If we let a touring machine that accepts the language M= ”SJSU”. We can see now that there is al least a touring machine that does not accept the language “the same strings written in ASCII as Professor Pollett would call solutions to this problem”. Now we can see that the language L is not empty, and it does not contain every Turing machine there exists. We have shown that L is not trivial, and it fulfills Rice's theorem. Second, according to the slides we need to show the following. Let P be a language such that there exist TM descriptions ⟨M⟩∈P and ⟨M'⟩∉P. Further assume that whenever we have two machines M1 and M2 such that L(M1)=L(M2), then we have ⟨M1⟩∈P iff ⟨M2⟩∈P. Then P is undecidable. We can simply prove this, if two machines recognize the same language one can recognize “the same strings written” while the others might not and the other way around. In other words, If there are two Turing Machines that recognize the same language, then both of the machines recognize ASCII or both do not recognize ASCII. Now, we have satisfied the second condition of Rice’s theorem and we can now use it. By the theorem, we have shown that “the same strings written in ASCII as Professor Pollett would call solutions to this problem” is undecidable

-- Practice Final Thread

Name: Gurseerat Singh '''Q10 Use Rice's theorem to show that the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable.''' According to the Rice Theorm Let P be a language such that there exists TM descriptions ⟨M⟩∈P and ⟨M'⟩∉P. Further assume that whenever we have two machines M1 and M2 such that L(M1)=L(M2), then we have ⟨M1⟩∈P iff ⟨M2⟩∈P. Then P is undecidable. Let us assume that we have a language L that is not empty and does not contain every Turing machine that exists so that L is not trivial. Now if we have two Turing machines that recognize the same language, it is impossible for one to recognize the language comprising "strings written in ASCII" that "Professor Pollett would call solutions to this problem" while the other does not, and similarly the other way around which satisfies the Second condition of the Rice’s theorem. Thus, using the Rice theorem we can show that the question of whether a Turing Machine correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable.