patternMajor
Church-Turing Thesis and computational power of neural networks
Viewed 0 times
thesisneuralandnetworkscomputationalpowerchurchturing
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#85377, answer score: 47
Revisions (0)
No revisions yet.