- 4 Shu Whey They Are Free And Don T Do Anything But To Their Print Thing Of Life The Other Calls Des Just Food Yue Doe 1 (30.1 KiB) Viewed 59 times
- 4 Shu Whey They Are Free And Don T Do Anything But To Their Print Thing Of Life The Other Calls Des Just Food Yue Doe 2 (57.79 KiB) Viewed 59 times
Sudpose vou're given two programs P and P. When vou trv running them it seems like
thev just run forever and don't do anvthing, but in fact one of them will eventuallv print Out
the meaning of life-the other one reallv does just run forever and do nothing. Unfortunately
you don't know which is which, and you also don't know how long the non-useless one takes
before finallv halting and printing the meaning of lite. Also unfortunatelv. vour computer
can onlv run one program at a time
So. how exactlv do vou go about achieving nirvana?
If vou get tired of waiting for the program currently
running to finish, vou can decide to
kill it after some amount of time vou choose and try running the other one awhile. You can
switch back and forth between running the two programs, but when vou restart a program
vou killed earlier it unfortunatelv starts over from scratch. It does not continue from where
it left off betore you killed it, but when you run it again you can try giving it a longer time
limit betore you kill it again..
Your task is: design an algorithm that, by calling P, and Pa as subroutines, will "efficiently"
hnd you the meaning of life.
Here's what efficient" means here: suppose the program that does eventually halt does so
after some (unknown) time T
If you knew which program this was, or if you had two
computers to run the two programs m parallel. or It vou coud restart a rram rom where
left off before vou killed it (which. recall. vou can't), then vou could learn the answer in
time O(T).
So vour goal is to design an algorithm whose running time (as a function of 1) is as small
as Possible.
Notice that we don't need to talk about primitive operations and so forth here: the running
time of vour algorithm is basicallv just the maximum total amount of time it will spend
running P, and P in the worst cast
(a) Give a e(T2)-time algorithm.
Give an @(I)-time algorithm.(Hint: What sort of sequence of numbers x1,..., xn sumsorder of xn, i.e., satisfies L"
Give an @(I)-time algorithm.
(Hint: What sort of sequence of numbers x1,..., xn sums
order of xn, i.e., satisfies L"
- 4 Shu Whey They Are Free And Don T Do Anything But To Their Print Thing Of Life The Other Calls Des Just Food Yue Doe 3 (57.79 KiB) Viewed 59 times
- 4 Shu Whey They Are Free And Don T Do Anything But To Their Print Thing Of Life The Other Calls Des Just Food Yue Doe 4 (8.2 KiB) Viewed 59 times
4. Suppose you're given two programs P and P. When you try running them it seems like they just run forever and don't do anything, but in fact one of them will eventually print out the meaning of life-the other one really does just run forever and do nothing. Unfortunately you don't know which is which, and you also don't know how long the non-useless one takes before finally halting and printing the meaning of life. Also unfortunately, your computer can only run one program at a time. So, how exactly do you go about achieving nirvana? If you get tired of waiting for the program currently running to finish, you can decide to kill it after some amount of time you choose and try running the other one awhile. You can switch back and forth between running the two programs, but when you restart a program you killed earlier it unfortunately starts over from scratch. It does not continue from where it left off before you killed it, but when you run it again you can try giving it a longer time limit before you kill it again... Your task is: design an algorithm that, by calling P, and P, as subroutines, will efficiently" find you the meaning of life. Here's what efficient" means here: suppose the program that does eventually halt does so after some (unknown) time T. If you knew which program this was, or if you had two computers to run the two programs in parallel, or if you could restart a program from where it left off before you killed it (which, recall, you can't), then you could learn the answer in time O(T). So your goal is to design an algorithm whose running time (as a function of T) is as small as possible. Notice that we don't need to talk about primitive operations and so forth here; the running time of your algorithm is basically just the maximum total amount of time it will spend running and in the worst case, (a) Give a e()-time algorithm.
(b) Give an (T)-time algorithm (Hint: What sort of sequence of mumbers .... sums up to a value that is on the order of , .. satisfies i = 0(x..)?)