Jason (jcreed) wrote,

Here's an old thread from a year or two ago on the FOM list (thanks to gustavolacerda for finding it) about "hypercomputation", the notion of computers that can do an infinite amount of what we think of as ordinary computation in a finite amount of time. For example, a machine that could solve the halting problem.

I haven't gotten through reading the whole thread, but I did already have a thought I wanted to record after reading the first message. Basically it asks (by alluding to a Marin Davis article that asks the same question) how would we ever know for sure that we have in front of us a machine that can do this "hypercomputation"? Hypercomputation entails some sort of infinite process, and we have only finite means. However, this objection is a bit premature, since I only have finite means to test whether a black-box machine is really computing multiplication, an "infinite" function in the sense that it is composed of infinitely many multiplication facts.

But I can imagine a definite candidate for an experiment that would persuade me that a machine is probably doing superTuring computation, as long as I believe P!=NP --- (frankly, I wouldn't turn down a physical machine that quickly solves NP problems as a christmas gift if the cosmic shopping mall is sold out of halting oracles :) I've already pretty much given away the task by formulating my assumptions: solve some NP-hard optimization problem. If the machine quickly spits out impressively good results, then I'll have some greater confidence that it's doing something mere Turing machines can't.

This probably has some hole in it still, but it's the first thing that came to mind...
Tags: theory
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded