2011-09-11
Q-5 .
'''Originally Posted By: Nishant'''
Hi,<br><br>I am not able to understand Q-5 i.e.<br>&quot;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.&quot;<br>Could anyone please provide some hint on this question ?<br>I just need a head start for this question.<br><br>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,<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
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.<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.
'''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) This Site - This Search Engine
Query Statistics
https://yioop.com/thread/3254
Total Elapsed Time for Queries: 0.04436540603637695 seconds.
Total Elapsed Time for Queries: 0.04436540603637695 seconds.
SELECT LOCALE_NAME, WRITING_MODE FROM LOCALE WHERE LOCALE_TAG ='en-US'
Time: 0.0003240108489990234 seconds.
SELECT COALESCE(MAX(UPDATE_TIMESTAMP), 0) AS MOST_RECENT FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID = 2 AND ITEM_TYPE = 3 AND ITEM_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = 2 AND STATUS = 1) AND UPDATE_PERIOD = -4
Time: 0.0003759860992431641 seconds.
DELETE FROM ITEM_IMPRESSION_SUMMARY
WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 3254 [2] => 1 )
Array ( [0] => 2 [1] => 3254 [2] => 1 )
Time: 0.0001521110534667969 seconds.
INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES
(?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 3254 [2] => 1 [3] => 1789978156 )
Array ( [0] => 2 [1] => 3254 [2] => 1 [3] => 1789978156 )
Time: 0.003834009170532227 seconds.
UPDATE ITEM_IMPRESSION_SUMMARY
SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND
ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2
AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 3254 [2] => 1 )
Array ( [0] => 2 [1] => 3254 [2] => 1 )
Time: 0.000102996826171875 seconds.
DELETE FROM ITEM_IMPRESSION_SUMMARY
WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 247 [2] => 3 )
Array ( [0] => 2 [1] => 247 [2] => 3 )
Time: 0.002362966537475586 seconds.
INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES
(?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 247 [2] => 3 [3] => 1789978156 )
Array ( [0] => 2 [1] => 247 [2] => 3 [3] => 1789978156 )
Time: 0.002147912979125977 seconds.
UPDATE ITEM_IMPRESSION_SUMMARY
SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND
ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2
AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 247 [2] => 3 )
Array ( [0] => 2 [1] => 247 [2] => 3 )
Time: 7.796287536621094E-5 seconds.
SELECT COUNT(GI.ID) AS NUM FROM GROUP_ITEM GI WHERE GI.GROUP_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = ? AND STATUS = 1) AND GI.TITLE NOT LIKE ? AND GI.PUBDATE > ?
Array ( [0] => 2 [1] => %2% [2] => 1789978152 )
Array ( [0] => 2 [1] => %2% [2] => 1789978152 )
Time: 0.0004000663757324219 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-4 )
Array ( [0] => -1 [1] => 2 [2] => 2-4 )
Time: 0.0001089572906494141 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-37 )
Array ( [0] => -1 [1] => 2 [2] => 2-37 )
Time: 3.695487976074219E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-202 )
Array ( [0] => -1 [1] => 2 [2] => 2-202 )
Time: 3.290176391601562E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-687 )
Array ( [0] => -1 [1] => 2 [2] => 2-687 )
Time: 3.290176391601562E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1115 )
Array ( [0] => -1 [1] => 2 [2] => 2-1115 )
Time: 3.504753112792969E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1138 )
Array ( [0] => -1 [1] => 2 [2] => 2-1138 )
Time: 5.292892456054688E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1140 )
Array ( [0] => -1 [1] => 2 [2] => 2-1140 )
Time: 3.695487976074219E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1149 )
Array ( [0] => -1 [1] => 2 [2] => 2-1149 )
Time: 3.194808959960938E-5 seconds.
SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1152 )
Array ( [0] => -1 [1] => 2 [2] => 2-1152 )
Time: 3.218650817871094E-5 seconds.
SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3254 )
Array ( [0] => 3254 )
Time: 9.894371032714844E-5 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 4.506111145019531E-5 seconds.
SELECT COUNT(DISTINCT GI.ID) AS NUM FROM GROUP_ITEM GI, SOCIAL_GROUPS G,
USER_GROUP UG, USERS O WHERE GI.PARENT_ID='3254' AND NOT LOWER(group_name) LIKE LOWER('Personal$%') AND (UG.USER_ID='2' OR G.REGISTER_TYPE IN ('4','3') ) AND GI.USER_ID=O.USER_ID AND
GI.GROUP_ID=G.GROUP_ID AND GI.GROUP_ID=UG.GROUP_ID AND ((
G.MEMBER_ACCESS IN ('2','3','4', '5')) OR
(G.OWNER_ID = UG.USER_ID OR UG.USER_ID = '1'))
Time: 0.0005609989166259766 seconds.
SELECT DISTINCT GI.ID AS ID,
GI.PARENT_ID AS PARENT_ID, GI.GROUP_ID AS GROUP_ID,
GI.TITLE AS TITLE, GI.DESCRIPTION AS DESCRIPTION,
GI.FLAG AS FLAG, GI.PUBDATE AS PUBDATE,
GI.EDIT_DATE AS EDIT_DATE, G.OWNER_ID AS OWNER_ID,
G.MEMBER_ACCESS AS MEMBER_ACCESS,
G.GROUP_NAME AS GROUP_NAME, P.USER_NAME AS USER_NAME,
P.USER_ID AS USER_ID, GI.TYPE AS TYPE, GI.UPS AS UPS,
GI.DOWNS AS DOWNS, G.VOTE_ACCESS AS VOTE_ACCESS
FROM GROUP_ITEM GI, SOCIAL_GROUPS G, USER_GROUP UG, USERS P
WHERE GI.PARENT_ID='3254' AND NOT LOWER(group_name) LIKE LOWER('Personal$%') AND (UG.USER_ID='2' OR G.REGISTER_TYPE IN ('4','3') ) AND GI.GROUP_ID=G.GROUP_ID AND GI.GROUP_ID=UG.GROUP_ID AND ((
G.MEMBER_ACCESS IN ('2','3','4', '5')) OR
(G.OWNER_ID = UG.USER_ID OR UG.USER_ID = '1')) AND GI.PARENT_ID NOT IN (SELECT DISCUSS_THREAD FROM GROUP_PAGE WHERE TITLE LIKE '%$$%' AND DISCUSS_THREAD IS NOT NULL) AND P.USER_ID = GI.USER_ID ORDER BY GI.PUBDATE ASC LIMIT 10 OFFSET 0
Time: 0.02803206443786621 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0004580020904541016 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001330375671386719 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001621246337890625 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001809597015380859 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001790523529052734 seconds.
SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3254 )
Array ( [0] => 3254 )
Time: 0.0003798007965087891 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0002090930938720703 seconds.
SELECT STATUS FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )
Array ( [0] => 2 )
Time: 0.0003859996795654297 seconds.
SELECT USER_NAME FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )
Array ( [0] => 2 )
Time: 0.0002589225769042969 seconds.
SELECT * FROM VISITOR WHERE ADDRESS = :address
AND PAGE_NAME = :page_name LIMIT 1
Array ( [:address] => 216.73.216.124 [:page_name] => forbidden_time_out )
Array ( [:address] => 216.73.216.124 [:page_name] => forbidden_time_out )
Time: 0.0002219676971435547 seconds.
SELECT COUNT(DISTINCT G.GROUP_ID) AS NUM FROM USER_GROUP UG, SOCIAL_GROUPS G WHERE UG.USER_ID = ? AND UG.GROUP_ID = G.GROUP_ID AND ( UG.STATUS = 1 OR UG.STATUS = 5)
Array ( [0] => 2 )
Array ( [0] => 2 )
Time: 0.0005171298980712891 seconds.
SELECT G.GROUP_ID AS GROUP_ID FROM SOCIAL_GROUPS G WHERE G.GROUP_NAME = ?
Array ( [0] => Personal$2 )
Array ( [0] => Personal$2 )
Time: 0.0001330375671386719 seconds.
SELECT USER_ID FROM USER_GROUP WHERE GROUP_ID = ?
Array ( [0] => -1 )
Array ( [0] => -1 )
Time: 6.198883056640625E-5 seconds.
SELECT G.GROUP_ID AS GROUP_ID,
G.GROUP_NAME AS GROUP_NAME,
G.OWNER_ID AS OWNER_ID, O.USER_NAME AS OWNER, REGISTER_TYPE,
UG.STATUS AS STATUS, G.MEMBER_ACCESS AS MEMBER_ACCESS,
G.VOTE_ACCESS AS VOTE_ACCESS, G.POST_LIFETIME AS POST_LIFETIME,
UG.JOIN_DATE AS JOIN_DATE, G.OPTIONS AS OPTIONS,
G.RENDER_ENGINE AS RENDER_ENGINE,
G.GROUP_THEME AS GROUP_THEME, G.PAGE_HEADER AS PAGE_HEADER,
G.PAGE_FOOTER AS PAGE_FOOTER
FROM SOCIAL_GROUPS G, USERS O, USER_GROUP UG WHERE (UG.USER_ID = :user_id) AND UG.GROUP_ID= :group_id AND UG.GROUP_ID=G.GROUP_ID AND OWNER_ID = O.USER_ID LIMIT 1
Array ( [:group_id] => 247 [:user_id] => 2 )
Array ( [:group_id] => 247 [:user_id] => 2 )
Time: 0.0001919269561767578 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => -2 )
Array ( [0] => -2 )
Time: 0.0003268718719482422 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0002400875091552734 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001621246337890625 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001568794250488281 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001568794250488281 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001509189605712891 seconds.
SELECT G.GROUP_ID AS GROUP_ID,
G.GROUP_NAME AS GROUP_NAME,
G.OWNER_ID AS OWNER_ID, O.USER_NAME AS OWNER, REGISTER_TYPE,
UG.STATUS AS STATUS, G.MEMBER_ACCESS AS MEMBER_ACCESS,
G.VOTE_ACCESS AS VOTE_ACCESS, G.POST_LIFETIME AS POST_LIFETIME,
UG.JOIN_DATE AS JOIN_DATE, G.OPTIONS AS OPTIONS,
G.RENDER_ENGINE AS RENDER_ENGINE,
G.GROUP_THEME AS GROUP_THEME, G.PAGE_HEADER AS PAGE_HEADER,
G.PAGE_FOOTER AS PAGE_FOOTER
FROM SOCIAL_GROUPS G, USERS O, USER_GROUP UG WHERE (UG.USER_ID = :user_id OR G.REGISTER_TYPE IN (3,4)) AND UG.GROUP_ID= :group_id AND UG.GROUP_ID=G.GROUP_ID AND OWNER_ID = O.USER_ID LIMIT 1
Array ( [:group_id] => 247 [:user_id] => 2 )
Array ( [:group_id] => 247 [:user_id] => 2 )
Time: 0.0005388259887695312 seconds.
SELECT STATUS FROM USER_GROUP WHERE
USER_ID=? AND GROUP_ID=? LIMIT 1
Array ( [0] => 2 [1] => 247 )
Array ( [0] => 2 [1] => 247 )
Time: 0.0002439022064208984 seconds.