2013-05-13
Final Practice Number 8 (Section 1).
Originally Posted By: sunny
Group Members
Jason Monroe
Tony Lam
Sunny Le
Wenyu Lin
Christina Viernes
L = {| M accepts inputs which are in PSPACE}
Rice's Theorem
1. There are encodings of M which are in PSPACE and encodings which are not in PSPACE
2. If the machines accept the same language either M1, M2 are elements of L or M1,M2 are not elements of L
The rejecting TM, Rej, which immediately rejects on all inputs is in PSPACE.
It never accepts anything outside of PSPACE, thus it's in the language.
Consider a TM which runs in exponential space, this TM is not in PSPACE by the Space Hierarchy Theorem.
Based on the Space Hierarchy Theorem, PSPACE does not contain exponential space, but exponential space does contain PSPACE.
Assume there is a M1 and M2 that accepts the language that is PSPACE. IF L(M1) = L(M2), then either they are both in L or they both are not. From here, we can see that since they both accept PSPACE, they are elements of L.
Jason Monroe
Tony Lam
Sunny Le
Wenyu Lin
Christina Viernes
L = {| M accepts inputs which are in PSPACE}
Rice's Theorem
1. There are encodings of M which are in PSPACE and encodings which are not in PSPACE
2. If the machines accept the same language either M1, M2 are elements of L or M1,M2 are not elements of L
The rejecting TM, Rej, which immediately rejects on all inputs is in PSPACE.
It never accepts anything outside of PSPACE, thus it's in the language.
Consider a TM which runs in exponential space, this TM is not in PSPACE by the Space Hierarchy Theorem.
Based on the Space Hierarchy Theorem, PSPACE does not contain exponential space, but exponential space does contain PSPACE.
Assume there is a M1 and M2 that accepts the language that is PSPACE. IF L(M1) = L(M2), then either they are both in L or they both are not. From here, we can see that since they both accept PSPACE, they are elements of L.
'''Originally Posted By: sunny'''
Group Members<br>Jason Monroe<br>Tony Lam<br>Sunny Le<br>Wenyu Lin<br>Christina Viernes<br><br><br><br><br><br><br>L = {| M accepts inputs which are in PSPACE}<br>Rice's Theorem<br>1. There are encodings of M which are in PSPACE and encodings which are not in PSPACE<br>2. If the machines accept the same language either M1, M2 are elements of L or M1,M2 are not elements of L<br><br>The rejecting TM, Rej, which immediately rejects on all inputs is in PSPACE.<br>It never accepts anything outside of PSPACE, thus it's in the language.<br><br>Consider a TM which runs in exponential space, this TM is not in PSPACE by the Space Hierarchy Theorem.<br>Based on the Space Hierarchy Theorem, PSPACE does not contain exponential space, but exponential space does contain PSPACE.<br><br>Assume there is a M1 and M2 that accepts the language that is PSPACE. IF L(M1) = L(M2), then either they are both in L or they both are not. From here, we can see that since they both accept PSPACE, they are elements of L.
2013-05-19
Originally Posted By: SimonKuo
Is the words below the image identical to the image?
Best regards,
Simon
Best regards,
Simon
'''Originally Posted By: SimonKuo'''
Is the words below the image identical to the image?<br><br>Best regards,<br>Simon
Originally Posted By: CViernes
The image above is what we wrote on the board during class time. He graded it and told us to re-do it. So, the written part below is our final and edited version of the answer.
'''Originally Posted By: CViernes'''
The image above is what we wrote on the board during class time. He graded it and told us to re-do it. So, the written part below is our final and edited version of the answer.
(c) 2024 Yioop - PHP Search Engine