100 Prisoners

There are 100 prisoners each with a unique name. There are 100 boxes, each one containing a single prisoner's name such that every name is in exactly one box. Each prisoner has to select and open up to 50 boxes and if his name is not in any of these 50 boxes then all the prisoners are executed. They go through this process one at a time, each prisoner finishing before the next begins. They can communicate to come up with a strategy before beginning, however, they cannot communicate in any way after the process has begun.

What is the best strategy that results in the prisoners' greatest chance of survival? Hint: It is greater than 30%. And if that's too easy, prove that this is the optimal strategy.

Non-Turing Computers are the New Non-Euclidean Geometries

Did the title confuse the hell out of you? Well then good, keep on reading.

The first International Conference on Infinity in Logic & Computation started today at UCT. Being on campus and with a recent interest in the theoretical side of Computer Science (I took two courses this year) I decided it would be worth attending. I won't lie, a lot of the talks went way over me as they were deeply theoretical. A lot of the talks today were on automata and infinite games -- something I have little background in. They were interesting nonetheless.

Tomorrows talks should be more what I'm into though with the computability and complexity talks. Although titles can be somewhat misleading if you're not rather clued up on the topic. This holds for the title of this post, which only starts to make sense after a little thinking.

Two of today's speakers didn't pitch and they both happened to be in the last session, leaving extra time for the last speaker. And boy did he need it! He starts off by presenting himself as a philosopher of physics. Now is a good a time as any to inform you that the title of this post was the title of has talk. So what does it mean? Well, this is non-Euclidean geometry. The important part is that it's not the standard geometry that we're all used to, but it works. Turing machines are computing devices that can solve any problem any other computer can solve (I shall ignore black holes in this post). So non-Turing computers refers to non-standard computing devices.

So what does all that mean? Here's the abstract of his talk:

It is argued that recent work on non-Turing computability suggests a picture of computability analogous to that of modern geometry, and that in this picture there is no fundamental (absolute) boundary between the computable and the uncomputable. If correct, a conjecture about this fictional boundary's precise location would merely reflect a misunderstanding. The Church-Turing thesis is just such a conjecture.

After his introduction he went onto define SAD computers. It uses some whacked spacetime theories or something (I'm no Physicist!). You take a different spacetime path to the modified Turning machine such that even if the Turing machine takes a billion years to compute an answer, you can take just a second to reach the point in spacetime where it finishes the computation. This is then extended to the idea of infinite computation to solve problems that are uncomputable on an ordinary Turing machine.

As a Computer Scientist that works on mostly practical problems this really pushed the boundaries of what I thought people studied on the theoretical side of things. I guess it gets far worse, but half of us seriously stared at the speaker with pale faces. With a little thought I can see why people study such topics, but it came as a bit of a shock to me when he first started.

To finish up, an interesting paradox he mentioned right at the end of his talk. You have a box. At time 0 you put ten balls numbered 1-10 into the box and then immediately remove the ball numbered 1. At time (1/2)t you add to the box balls numbered 11-20 and at the same time remove the ball numbered 2. At time (3/4)t add 21-30 and remove 3. At time (7/8)t add 31-40 and remove 4. And so on, and so on... How many balls in the box at time t?

Riddle: Sink the Sub

A friend was asked the following riddle in a Google interview yesterday. I found it quite interesting. If you have the right background it is trivial, however, if you do not then it can be rather tricky. Feel free to post a solution.

An enemy submarine is somewhere on the number line (consider only integers for this problem). It is moving at some rate (again, integral units per minute). You know neither its position nor its velocity.

You can launch a torpedo each minute at any integer on the number line. If the the submarine is there, you hit it and it sinks. You have all the time and torpedoes you want. You must sink this enemy sub - devise a strategy that is guaranteed to eventually hit the enemy sub.

Note: This was copied from here. That page contains at least one other questions I was asked in my interviews with Google.