6
$\begingroup$

A few weeks ago, I came upon this great post by JDH and it has been troubling me ever since. The TL;DR for the proof is that we can encode the outputs of any function into the axioms of a set theory so that we simply require a single Turing Machine capable of acting as a clever "parser" which can extract the information from the axioms and compute the desired function - this I understand (at least, conceptually and somewhat formally).

What confuses me though is the philosophical implications this has for conceptions of computability... I believed that there was, in some sense, a universal notion of computability (i.e. there were problems that either are or aren't decidable) but this suggests that such notions depend on the set-theoretic background for your computation - for example, this post by Scott Aaronson discusses the work of one of his students in showing that there is a specific Turing Machine whose behaviour is independent of ZFC (suggesting again, implicitly, that the behaviour is platonic but that we simply can't prove it either way).

Forgive me for my lack of well-definedness in my question but: Is there a way in which this can be resolved? Why are there seemingly uncomputable problems (whose proof of uncomputability often use proofs by contradiction seemingly without reference to any set-theoretic background, e.g. the Halting Problem) which can be computed by a Turing Machine, without the use (officially) of an oracle? Does this have any impact on the Church-Turing Thesis, as presumably no human could compute reliably the Busy Beaver function while the universal algorithm (if put in the right universe) can?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

You may have misunderstood one of the key aspects of that post by Hamkins. His theorem does not say that every function is computable (despite the title).

It says, instead, that for any given function, you can compute it in some carefully chosen universe, meaning in some carefully chosen model of set theory. The universe in which you can compute it will vary depending on the function. There are many, many, many different models of set theory, i.e many different set theoretic universes (just like there are many, many, many different models of group theory, i.e. many different groups). The function you were given may be computable in some models and uncomputable in others. All the theorem guarantees is the existence of some model in which the given function is computable.

$\endgroup$
5
  • $\begingroup$ Wouldn't it be helpful to substitute parallel computation in this universe for serial computation simultaneously progressing across multiple universes? $\endgroup$
    – James Arathoon
    Apr 25, 2018 at 13:02
  • 3
    $\begingroup$ Even saying that "you can compute it" in some carefully chosen universe seems to be dangerously suggestive here. What this really means is that there's a certain arithmetic sentence that (a) when interpreted in the actual integers expresses the claim that the specified Turing machine gives such-and-such output for such-and-such input, and (b) the sentence happens to be true about the carefully chosen universe. $\endgroup$
    – hmakholm left over Monica
    Apr 25, 2018 at 13:16
  • $\begingroup$ Your "dangerous suggestion" comment is apt, thanks. But probably I cannot do justice to the finer aspects of this issue, so I think I'll leave my answer as it is, hoping that the OP can perceive the dangerous waters that their post is treading into. $\endgroup$
    – Lee Mosher
    Apr 25, 2018 at 14:10
  • $\begingroup$ @Lee Mosher: Sorry for asking so long after this question was asked, but could you explain to me how this effects things like the Halting Problem? Does its proof only work because of certain (hidden/implicit) assumptions that rely on some standard model of ZFC or something? $\endgroup$
    – Isky Mathews
    May 7, 2018 at 16:35
  • 1
    $\begingroup$ @IskyMathews: It doesn't really have any effects on the halting problem. If you apply the construction to the halting function you get a special universe that (a) has non-standard integers and (b) has a Turing machine in it, such that the result the special universe thinks its Turing machine gives on the number of a standard finite Turing machine that will fit in your world, will match whether that machine terminates when run in your world. That answer may be wrong about running the machine in the special world itself, and you're guaranteed nothing about machines with nonstandard numbers. $\endgroup$
    – hmakholm left over Monica
    Jul 20, 2018 at 13:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.