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?
Posts
Cool paradox. I am going to post the solution here, so don't read if you want to work it out yourself:
ReplyDeleteThe answer is, of course, that there are no balls in the box at time t. If there were a ball in the box, it must have a number. Call this number N. In the first iteration, ball number 1 is removed. In the second iteration, ball number 2 is removed... In the Nth iteration, ball number N is removed. Therefore ball N cannot be in the box. Since N was arbitrary, this implies no ball can be in the box.
Now let me change the problem slightly. I will take away the numbers on the balls. So, at time 0 I put 10 arbitrary balls in the box and remove any one of them. At time (1/2)t I put 10 more balls in the box and remove one, and so on. How many balls are there now at time t?
It is clear that at time t I now have an infinite number of balls in the box. There is no sleight of hand that can save me from this conclusion. In each iteration I add 10-1 = 9 balls to the box, so the total number of balls will increase indefinitely. But all I have done is removed the labels from the balls - everything else remains the same. Just by labeling the balls, the outcome changes.
Perfect solution, and you even identified the second half of the paradox! One nitpick though -- is it really the labelling of the balls or is it rather the ordering of the removal process that changes the outcome, i.e. "remove any one of them"? We could retain the labels and change the removal process to "remove a random ball" and we would get the infinite result. As I said though, it's being picky.
ReplyDeleteAnother paradox he mentioned. A light is on at time 0, off at time (1/2)t, on at time (3/4)t and so on. What is the state of the light at time t?