2013-05-19
Practice Final #8 Section 3.
Originally Posted By: LeonardNg
(Erik postring)
Use Rice's theorem to show the set of encoding of TMs that recognize a language in PSPACE is undecidable.
We need to establish about L two things to apply Rice's Theorem:
1. There are some ∈ L and some ∉ L.
2. If we have two machines M1 and M2 such that L(M1) = L(M2), then we have ∈ L iff ∈ L. Also note that if L(M1) = L(M2) then both M1,M2 ∈ L or both M1,M2 ∉ L.
To see (1) notice that the machine Rej which immediately rejects, doesn't accept any input, is in PSPACE and thus in the language. On the other hand, a machine that writes it's input of length n, n times will accept in n^n space which is exponential and not in PSPACE. To see (2) notice that if two TM's M1 and M2 have the same language then that language wither accepts in PSPACE or it doesn't. If it doesn't then both M1 and M2 would not be in L, and if it does then both M1 and M2 would be in L. Hence (2) holds. Since both the prerequisites of Rice's Theorem hold, we therefore have by Rice's Theorem that L is undecidable.
Three other members contributed to this answer, I am unsure of their names, please post your name as a response.
Use Rice's theorem to show the set of encoding of TMs that recognize a language in PSPACE is undecidable.
We need to establish about L two things to apply Rice's Theorem:
1. There are some ∈ L and some ∉ L.
2. If we have two machines M1 and M2 such that L(M1) = L(M2), then we have ∈ L iff ∈ L. Also note that if L(M1) = L(M2) then both M1,M2 ∈ L or both M1,M2 ∉ L.
To see (1) notice that the machine Rej which immediately rejects, doesn't accept any input, is in PSPACE and thus in the language. On the other hand, a machine that writes it's input of length n, n times will accept in n^n space which is exponential and not in PSPACE. To see (2) notice that if two TM's M1 and M2 have the same language then that language wither accepts in PSPACE or it doesn't. If it doesn't then both M1 and M2 would not be in L, and if it does then both M1 and M2 would be in L. Hence (2) holds. Since both the prerequisites of Rice's Theorem hold, we therefore have by Rice's Theorem that L is undecidable.
Three other members contributed to this answer, I am unsure of their names, please post your name as a response.
'''Originally Posted By: LeonardNg'''
(Erik postring)<br><br>Use Rice's theorem to show the set of encoding of TMs that recognize a language in PSPACE is undecidable.<br><br>We need to establish about L two things to apply Rice's Theorem:<br>1. There are some ∈ L and some ∉ L.<br>2. If we have two machines M1 and M2 such that L(M1) = L(M2), then we have ∈ L iff ∈ L. Also note that if L(M1) = L(M2) then both M1,M2 ∈ L or both M1,M2 ∉ L.<br><br>To see (1) notice that the machine Rej which immediately rejects, doesn't accept any input, is in PSPACE and thus in the language. On the other hand, a machine that writes it's input of length n, n times will accept in n^n space which is exponential and not in PSPACE. To see (2) notice that if two TM's M1 and M2 have the same language then that language wither accepts in PSPACE or it doesn't. If it doesn't then both M1 and M2 would not be in L, and if it does then both M1 and M2 would be in L. Hence (2) holds. Since both the prerequisites of Rice's Theorem hold, we therefore have by Rice's Theorem that L is undecidable. <br><br>Three other members contributed to this answer, I am unsure of their names, please post your name as a response.
Originally Posted By: matthew
Matthew Somers
Raymond Ancheta
Wesley Eversole
Good work Erik!
Raymond Ancheta
Wesley Eversole
Good work Erik!
'''Originally Posted By: matthew'''
Matthew Somers<br>Raymond Ancheta<br>Wesley Eversole<br><br>Good work Erik!
(c) 2024 Yioop - PHP Search Engine