Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the answer is well known).

Has anyone looked at an extension of the Turing machine outside of discrete mathematics? For example, things like extending the way the symbol table works so that the symbol table is actually an N dimensional space that for any given real number valued input X stored on the tape it computes F(X, NCoordinates) as an output and uses G(X, NCoordinates) to move to a new space inside the "symbol space", possibly not happening in discrete steps, but continuously?

It seems to me that such a model would be physically realizable for some kinds of functions F, and G, and that it would clearly solve some problems faster than a Turing machine. (Obviously, I've defined it so broadly that you can just define F and G such that they are directly the problem you are trying to solve. (Which amounts to saying that if you want to build a computer to decide how many tornadoes the earth will have in the next 5 years, the earth is a pretty good one, but it will take 5 years to compute).). But one could investigate classes of F and G that might be realizable by a human built computer.

And as far as applying this to math, things like the best known proofs of the incompleteness theorem define computation as manipulating discrete sets of symbols. Is it mathematically coherent to think about what could be proven using the kind of augmented Turing machine I just described? Of course, such "proofs" could not be written down using symbols, but can we imagine how they might work?

Or have I just found a roundabout way of describing analog computing, and it's not interesting at all?

  • 1
    $\begingroup$ There's the Blum-Shub-Smale machine model for computations over real numbers. $\endgroup$ – Srivatsan Sep 1 '11 at 18:34
  • $\begingroup$ @Srivatsan - thank you $\endgroup$ – psr Sep 1 '11 at 18:58
  • $\begingroup$ There are several different models of computation over real numbers, BSS is just one of them. But they all use the same model of TM, just with different semantics. $\endgroup$ – Yuval Filmus Sep 1 '11 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.