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.04341554641723633 seconds.
Total Elapsed Time for Queries: 0.04341554641723633 seconds.
SELECT LOCALE_NAME, WRITING_MODE FROM LOCALE WHERE LOCALE_TAG ='en-US'
Time: 0.0004448890686035156 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.0003819465637207031 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.003537178039550781 seconds.
INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES
(?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 3254 [2] => 1 [3] => 1789980853 )
Array ( [0] => 2 [1] => 3254 [2] => 1 [3] => 1789980853 )
Time: 0.002164125442504883 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.0001220703125 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.002060890197753906 seconds.
INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES
(?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 247 [2] => 3 [3] => 1789980853 )
Array ( [0] => 2 [1] => 247 [2] => 3 [3] => 1789980853 )
Time: 0.002202033996582031 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: 0.0001060962677001953 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] => 1789980846 )
Array ( [0] => 2 [1] => %2% [2] => 1789980846 )
Time: 0.0002880096435546875 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.0001039505004882812 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: 4.696846008300781E-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.600120544433594E-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.480911254882812E-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.409385681152344E-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.412101745605469E-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.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-1149 )
Array ( [0] => -1 [1] => 2 [2] => 2-1149 )
Time: 3.385543823242188E-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.385543823242188E-5 seconds.
SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3254 )
Array ( [0] => 3254 )
Time: 8.296966552734375E-5 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 4.792213439941406E-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.0006289482116699219 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.02794599533081055 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 0.0001890659332275391 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 3.099441528320312E-5 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 2.503395080566406E-5 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 2.288818359375E-5 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 3.099441528320312E-5 seconds.
SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3254 )
Array ( [0] => 3254 )
Time: 0.0001299381256103516 seconds.
SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 4.887580871582031E-5 seconds.
SELECT STATUS FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )
Array ( [0] => 2 )
Time: 0.0001349449157714844 seconds.
SELECT USER_NAME FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )
Array ( [0] => 2 )
Time: 0.0004780292510986328 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.0003728866577148438 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.0005121231079101562 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.0001370906829833984 seconds.
SELECT USER_ID FROM USER_GROUP WHERE GROUP_ID = ?
Array ( [0] => -1 )
Array ( [0] => -1 )
Time: 6.508827209472656E-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.0002040863037109375 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => -2 )
Array ( [0] => -2 )
Time: 9.489059448242188E-5 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 2.312660217285156E-5 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 8.797645568847656E-5 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 2.408027648925781E-5 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 2.47955322265625E-5 seconds.
SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 247 )
Array ( [0] => 247 )
Time: 2.598762512207031E-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 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.0002608299255371094 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: 6.604194641113281E-5 seconds.