1. Suppose you're given two programs Pi and P2. 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 Pi and Py 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 smal 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 P2 in the worst case. (a) Give a (T2)-time algorithm