The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)$. From this, they claim in the conclusion that

This result shows that there is at least one fixed algorithm that can be distributedly run on networked randomly generated universal Turing machines, so that the entire algorithmic network can compute a function in the Turing degree $0'$, if the population/network size in large enough.

However, each network solves the Halting problem only for programs of bounded size, a restriction that makes the problem computable (For finitely many programs, there exists a look-up table that tells whether each of those programs halts). So, 'large enough' here has to mean some sort of infinity, and I do not really see how their construction extends to networks of infinite size. Am I misunderstanding their claim?

If (as I suspect), this network indeed does not solve an uncomputable problem, I also wonder whether this result is relevant to the notion of computability at all?

$^1$: Apparently, a halting oracle is involved as well, see section 4.2 in the paper. The authors even claim

... the oracle is only necessary to deal with the non-halting computations.

(emphasis mine) This confuses me greatly, because isn't the fact that there are non-halting computations the entire point? Also, if we are using an oracle for the halting problem anyway, why not use the oracle directly? However, even if we assume that this oracle is not nessecary, I still do not see why the main claim would hold.

  • 2
    $\begingroup$ Why are you wasting your time with this stuff? $\endgroup$ – Andrej Bauer Apr 19 at 19:00
  • $\begingroup$ @AndrejBauer Because I would be interested in this if it isn't nonsense, and can't quite tell how much nonsense it is. $\endgroup$ – Discrete lizard Apr 20 at 10:32
  • 1
    $\begingroup$ It sure looks like nonsense. If it isn't they hid the good bits really well. $\endgroup$ – Andrej Bauer Apr 20 at 12:31
  • $\begingroup$ @AndrejBauer I only gave the introduction and conclusion a quick reading, but it isn't obviously nonsense to me, apart from the badly-worded abstract. I guess you're implying that these are cranks who make an obviously incorrect mathematical claim (solving the halting problem with Turing-equivalent computation), but that's not what they claim: they claim a result about propagating knowledge from oracles over a network. It looks more like a result about complexity than about computability: if you have a network of halting oracles and Turing machines, how do the oracular results propagate? $\endgroup$ – Gilles Apr 20 at 23:19
  • $\begingroup$ @Gilles I have read a bit more of the paper and the definitions, theorems and proofs all seem sane and sound at a glance. It is mostly the interpretation of their results that sounds off. I indeed think that their claims regarding undecidability are unfounded, but I'm not that familiar with computability theory to be sure, which is why I asked this question. Another strange part is that it seems a node must run a program until $BB(x)$, which means their procedure has another 'non-constructive' part apart from the initial oracles. $\endgroup$ – Discrete lizard Apr 21 at 10:37

If we take 'in the limit' to mean 'a network (countably) infinite number of Turing machines', then the answer is yes, but a network of an infinite number of bits would also do.

We take some an ordering on all Turing machines. Since the number of Turing machines is only countably infinite, for each Turing machine, we can assign '0' to bit $n$ if Turing machine $n$ halts and '1' if it does not. (It does not matter that we don't know if we should put 0 or 1, since there exists a correct assignment, there exists a correct 'algorithm'. Since we don't have an infinite number of Turing machines anyway, I'm ok with a non-constructive 'algorithm') The 'network' then simply looks up the result at the $n$th bit when given Turing machine $n$ as input.


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.