Put another way: Can every mathematical proof be reformulated to be about some class of Turing Machines?


Any proof of the existence of infinite prime numbers is equivalent to the statement: "Any Turing Machine whose instructions amount to 'print the highest prime number' does not halt."

I say they are equivalent because any proof of the existence of infinite primes seems to verify the statement about the Turing Machine, and vice versa.

I feel like I can certainly do this with any algebraic, geometric, arithmetic, question that I am aware of.

I am considering putting such a remark into a paper I'm writing, but I'm not sure if such a remark is:

a) Obvious b) True, but requires the articulation of sophisticated ideas. In this case, I would love a reference. c) Subjective or at least philosophically contentious d) False, but requires the articulation of sophisticated ideas. e) Obviously False

  • 6
    $\begingroup$ If you're not sure about it, don't put it in your paper. $\endgroup$ – Asaf Karagila Sep 4 '15 at 21:53
  • $\begingroup$ That doesn't seem to be a trivial statement. Translation: don't state that as something everybody should know. For instance, what happens to the continuum hypothesis? Are axiom systems therefore "Turing-Complete"? I don't know if that last one is even appropriate to say. $\endgroup$ – Zach466920 Sep 4 '15 at 22:01
  • $\begingroup$ Are you claiming you can construct a Turing Machine whose 'instructions [provably] amount to "print the highest prime number"'? How does it test whether a number is the highest prime? $\endgroup$ – Rob Arthan Sep 4 '15 at 22:07
  • $\begingroup$ I'm thinking of extended models of Turing Machines, say with oracles. Let there be a "Last Prime Oracle." Feed it any integer and it returns 1 if it's the highest prime number, and 0 if it is not. The Turing Machine that runs "Print the highest prime number" simply checks each integer in order to see if it's the last prime and prints it if it is. Maybe this really changes the question. $\endgroup$ – Eric Bahr Sep 4 '15 at 22:12
  • 1
    $\begingroup$ So if you are admitting oracles to deal with computationally problematic questions, what insight does your observation give us? $\endgroup$ – Rob Arthan Sep 4 '15 at 22:31

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.