2011-05-16
practice final problem 3.
Originally Posted By: chinukamboj
if L runs in TIME(k.n)
=>there is a turing machine,M that runs on any string w (such that w is in L) in time k.n
Now we make another machine N by expanding M such that k moves of M are simulated by 1 move of N.
=> N is a turing machine that runs on any string w(in L) in time n
=> Time(n) is contained in UkTIME(k.n) because every string in the language in that runs in UkTIME(k.n) can be reduced to one that runs in TIME(n)
we know that TIME(n) is contained in ∪kTIME(k⋅n)), and because a multi - tape turing machine can be simulated on a single tape, we know that ∪kTIME(k⋅n)) has the same language as TIME(n) .
this simulation from multi-tape to single tape essentially lays the tapes sequentially on the single tape, which does involve a time penalty.
one example of this is palindromes. intuitively, this would be an easy problem to figure out given two tapes, because one can just go back and forth to check. However, on a single tape we are forced to check one square, then skip over and to the simulation of the second tape and go back again. the longer the palindrome gets, the further the time to travel (back and forth) becomes.
overall, while a 2-tape machine can compute palindromes in 4n, a one tape simulation requires as much as omega(n^2)
w | a | n | a | w
lambart, Gobinder Kamboj, raghav baldania, caterinal petre
=>there is a turing machine,M that runs on any string w (such that w is in L) in time k.n
Now we make another machine N by expanding M such that k moves of M are simulated by 1 move of N.
=> N is a turing machine that runs on any string w(in L) in time n
=> Time(n) is contained in UkTIME(k.n) because every string in the language in that runs in UkTIME(k.n) can be reduced to one that runs in TIME(n)
we know that TIME(n) is contained in ∪kTIME(k⋅n)), and because a multi - tape turing machine can be simulated on a single tape, we know that ∪kTIME(k⋅n)) has the same language as TIME(n) .
this simulation from multi-tape to single tape essentially lays the tapes sequentially on the single tape, which does involve a time penalty.
one example of this is palindromes. intuitively, this would be an easy problem to figure out given two tapes, because one can just go back and forth to check. However, on a single tape we are forced to check one square, then skip over and to the simulation of the second tape and go back again. the longer the palindrome gets, the further the time to travel (back and forth) becomes.
overall, while a 2-tape machine can compute palindromes in 4n, a one tape simulation requires as much as omega(n^2)
w | a | n | a | w
lambart, Gobinder Kamboj, raghav baldania, caterinal petre
'''Originally Posted By: chinukamboj'''
if L runs in TIME(k.n)<br>=>there is a turing machine,M that runs on any string w (such that w is in L) in time k.n<br>Now we make another machine N by expanding M such that k moves of M are simulated by 1 move of N. <br>=> N is a turing machine that runs on any string w(in L) in time n<br>=> Time(n) is contained in UkTIME(k.n) because every string in the language in that runs in UkTIME(k.n) can be reduced to one that runs in TIME(n)<br><br> we know that TIME(n) is contained in ∪kTIME(k⋅n)), and because a multi - tape turing machine can be simulated on a single tape, we know that ∪kTIME(k⋅n)) has the same language as TIME(n) . <br> this simulation from multi-tape to single tape essentially lays the tapes sequentially on the single tape, which does involve a time penalty. <br> one example of this is palindromes. intuitively, this would be an easy problem to figure out given two tapes, because one can just go back and forth to check. However, on a single tape we are forced to check one square, then skip over and to the simulation of the second tape and go back again. the longer the palindrome gets, the further the time to travel (back and forth) becomes. <br> overall, while a 2-tape machine can compute palindromes in 4n, a one tape simulation requires as much as omega(n^2)<br><br>w | a | n | a | w <br><br>lambart, Gobinder Kamboj, raghav baldania, caterinal petre
2011-05-18
This statement:
we know that TIME(n) is contained in ∪kTIME(k⋅n)), and because a multi - tape turing machine can be simulated on a single tape, we know that ∪kTIME(k⋅n)) has the same language as TIME(n) .
does not follow.
The stuff before this hinting at the linear speed-up theorem would get partial credit. The palindrome example is correct.
we know that TIME(n) is contained in ∪kTIME(k⋅n)), and because a multi - tape turing machine can be simulated on a single tape, we know that ∪kTIME(k⋅n)) has the same language as TIME(n) .
does not follow.
The stuff before this hinting at the linear speed-up theorem would get partial credit. The palindrome example is correct.
This statement:<br><br>we know that TIME(n) is contained in ∪kTIME(k⋅n)), and because a multi - tape turing machine can be simulated on a single tape, we know that ∪kTIME(k⋅n)) has the same language as TIME(n) . <br><br>does not follow.<br><br>The stuff before this hinting at the linear speed-up theorem would get partial credit. The palindrome example is correct.
(c) 2024 Yioop - PHP Search Engine