2011-09-11
Q-5.
Originally Posted By: Nishant
Hi,
I am not able to understand Q-5 i.e.
"show the problem of determining whether the second work tape of a TM ever has the string 0110 on it during the course of its computation is undecidable."
Could anyone please provide some hint on this question ?
I just need a head start for this question.
Thanks.
I am not able to understand Q-5 i.e.
"show the problem of determining whether the second work tape of a TM ever has the string 0110 on it during the course of its computation is undecidable."
Could anyone please provide some hint on this question ?
I just need a head start for this question.
Thanks.
'''Originally Posted By: Nishant'''
Hi,<br><br>I am not able to understand Q-5 i.e.<br>"show the problem of determining whether the second work tape of a TM ever has the string 0110 on it during the course of its computation is undecidable."<br>Could anyone please provide some hint on this question ?<br>I just need a head start for this question.<br><br>Thanks.
Hey Nishant,
Try to give a proof by contradiction. Suppose you could have a TM doing what the problem stipulates. Use this TM to decide
the Halting problem. i.e., reduce the halting problem to this one.
Best,
Chris
Try to give a proof by contradiction. Suppose you could have a TM doing what the problem stipulates. Use this TM to decide
the Halting problem. i.e., reduce the halting problem to this one.
Best,
Chris
Hey Nishant,<br><br>Try to give a proof by contradiction. Suppose you could have a TM doing what the problem stipulates. Use this TM to decide<br>the Halting problem. i.e., reduce the halting problem to this one.<br><br>Best,<br>Chris
Originally Posted By: Nishant
There are 2 things that I can think of.
1.) String is palindrome(this is how i am thinking) 0110. On Qstart it takes the input 0 and goes to state say Q1 and then it takes the next input as 1 and stays on the same state Q1.
or
2.) On Qstart it takes the input 0 and goes to state say Q1 and then it takes the next input as 1 and goes to the next state Q2 and takes the input 1 and goes back to the previous state and some how remains in that loop.
I am not sure whether it has something to do with the palindrome or not.
Also, kindly confirm whether I am on the right track or not.
1.) String is palindrome(this is how i am thinking) 0110. On Qstart it takes the input 0 and goes to state say Q1 and then it takes the next input as 1 and stays on the same state Q1.
or
2.) On Qstart it takes the input 0 and goes to state say Q1 and then it takes the next input as 1 and goes to the next state Q2 and takes the input 1 and goes back to the previous state and some how remains in that loop.
I am not sure whether it has something to do with the palindrome or not.
Also, kindly confirm whether I am on the right track or not.
'''Originally Posted By: Nishant'''
There are 2 things that I can think of.<br>1.) String is palindrome(this is how i am thinking) 0110. On Qstart it takes the input 0 and goes to state say Q1 and then it takes the next input as 1 and stays on the same state Q1.<br>or<br>2.) On Qstart it takes the input 0 and goes to state say Q1 and then it takes the next input as 1 and goes to the next state Q2 and takes the input 1 and goes back to the previous state and some how remains in that loop.<br><br>I am not sure whether it has something to do with the palindrome or not. <br>Also, kindly confirm whether I am on the right track or not.
Please use my hint in trying to solve the problem. What you wrote has no connection to my hint, so should be a sign you are on the wrong track. The solution has nothing to do with the fact the string happened to be palindrome.
Please use my hint in trying to solve the problem. What you wrote has no connection to my hint, so should be a sign you are on the wrong track. The solution has nothing to do with the fact the string happened to be palindrome.
As another hint on how to think about the problem.. Suppose you as a human were given a black box for the problem in the question, how could you use the black box to answer questions about the halting problem? Take your human algorithm and reimplement it as a Turing Machine.
As another hint on how to think about the problem.. Suppose you as a human were given a black box for the problem in the question, how could you use the black box to answer questions about the halting problem? Take your human algorithm and reimplement it as a Turing Machine.
(c) 2024 Yioop - PHP Search Engine