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?