Question 2:

You are playing a video game under the following idealized conditions. The computer memory is unbounded, and you have no time limit for finishing the game. The game board is the set of points in the plane with integer coordinates and time moves in discrete integer steps. There is a hidden submarine: you do not know its location; you do not know its speed and you do not know its direction of motion. The speed and direction of motion do not change throughout the game. The speed is a natural number and the direction of motion is either "up", "down", "left" or "right". For example, the submarine could start at (2, 3) have speed 7 and move right. Then at step 0 it is at (2, 3), at step 1 it is at (9, 3), at step 2 it is at (16, 3) and so on. At every step you get to zap a point: you enter the coordinates and if the submarine is at that point, at that time step, you will destroy it. Of course, there is no point zapping a position before it gets there or after it leaves. Give a strategy or scheme that is guaranteed to get the submarine at some finite stage. I repeat, you do not know where it started, you do not not know its direction and you do not know its speed; you only know that the speed and direction do not change. You get zero points for this question if your strategy works probabilistically; this question has nothing to do with probability.

Question 3:

A typical activity in Turing-machine programs includes "shifting over." Ideally, we might want to make an additional cell at the current head position, in which we could store some character. Be that as it may, we can't alter the tape along these lines. Or maybe, we need to move the contents of each of the cells to the right of the current head position one cell right, and afterward discover our way back to the current head position. Find and show the best way to complete the operation.

pur-new-sol

Related Questions