31
$\begingroup$

The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine. The paper "Analog computation via neural networks" (Siegelmannn and Sontag, Theoretical Computer Science, 131:331–360, 1994; PDF) claims that a neural net of a certain form (the settings are presented in the paper) is more powerful. The authors say that, in exponential time, their model can recognize languages that are uncomputable in the Turing machine model.

Doesn't this contradict the Church-Turing thesis?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
47
$\begingroup$

No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the power beyond that of a Turing Machine. In fact, the title of 1.2.2 is "The meaning of (non computable) real weight", where they discuss why their model is built to include non-computable components.

There are in fact many models of computation that exceed the power of Turing Machines (q.v. Hypercomputation). The catch is that none of these are apparently able to be constructed in the real world (but maybe in the $\mathbb{R}$ world - sorry, couldn't resist).

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ +1 at least partially for the concluding pun! $\endgroup$
    – Omar
    Dec 12, 2017 at 13:53
  • 2
    $\begingroup$ It's interesting to me that this seems to be related to the question of whether or not the Universe is digital and other questions of quantum mechanics like the fundamental uncertainty of a system. $\endgroup$
    – Omnifarious
    Dec 12, 2017 at 17:50
  • 7
    $\begingroup$ I'd add that $\mathbb{R}$ cannot exists in real world due to Bekenstein bound so QM prohibits such constructs. $\endgroup$
    – Maciej Piechotka
    Dec 12, 2017 at 22:50
  • 1
    $\begingroup$ I feel like the pun actually adds something to this answer, since it's such a widespread naive misunderstanding that the real numbers are real. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Dec 14, 2017 at 3:55
25
$\begingroup$

To expand a little on Luke's answer, physically building a neural net to solve any language requires producing electronic components with infinitely precise resistances and so on. This isn't possible, in multiple ways:

  1. You can't produce a resistor of exactly $\mathrm{2\,\Omega}$.

  2. Resistance changes with temperature and current flowing through the resistor will change its temperature.

  3. Even supposing that you know an electronic engineer/sorcerer who can produce resistors to any exact value you choose and that don't change resistance with temperature, setting up your machine to decide an uncomputable language will require uncomputable resistance values. So there's no way you could actually tell your electronic engineer/sorcerer what resistance value you need.

So, although, in principle, these machines can decide any language, they don't violate Church–Turing because they can't be physically constructed.

You might want to engage in some rules-lawyering and claim that somebody could hand you one of these machines and say, "Hey, look, this machine just happens to have exactly the right resistance values to solve the halting problem!" However, they have no way of proving this claim, since they can't measure the components to infinite precision, so the best they can claim with justification is "I tested this on some finite set of inputs and it correctly decided the halting problem on those inputs." Well, any finite subset of the halting problem is already Turing-decidable so that's nothing exciting.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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