Tese de Church-Turing e poder computacional das redes neurais

A tese de Church-Turing afirma que tudo o que pode ser fisicamente calculado, pode ser computado em uma máquina de Turing. O artigo "Computação analógica via redes neurais" (Siegelmannn e Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) afirma que uma rede neural de uma determinada forma (as configurações são apresentadas no artigo) é mais poderosa. Os autores afirmam que, no tempo exponencial, seu modelo pode reconhecer linguagens que são incontestáveis ​​no modelo da máquina de Turing.

Isso não contradiz a tese de Church-Turing?

Não, ainda é consistente com a tese de Church-Turing, o modelo deles vem equipado com números reais genuínos (como em elementos arbitrários de ), que praticamente imediatamente estendem o poder além do de uma máquina de Turing. De fato, o título de 1.2.2 é "O significado de peso real (não computável)", onde eles discutem por que seu modelo é construído para incluir componentes não computáveis.$\mathbb{R}$

De fato, existem muitos modelos de computação que excedem o poder das Máquinas de Turing (qv Hipercomputação ). O problema é que aparentemente nenhum deles pode ser construído no mundo real (mas talvez no mundo - desculpe, não pude resistir).$\mathbb{R}$

Para expandir um pouco a resposta de Lucas , construir fisicamente uma rede neural para resolver qualquer linguagem requer a produção de componentes eletrônicos com resistências infinitamente precisas e assim por diante. Isso não é possível, de várias maneiras:

1. Você não pode produzir um resistor exatamente .$\mathrm{2\,\Omega}$

2. A resistência muda com a temperatura e a corrente que flui através do resistor altera sua temperatura.

3. Mesmo supondo que você conheça um engenheiro / feiticeiro eletrônico que possa produzir resistores com o valor exato que você escolher e que não mude a resistência com a temperatura, configurar sua máquina para decidir uma linguagem não-confiável exigirá valores de resistência não-confiáveis. Portanto, não há como dizer ao engenheiro / feiticeiro eletrônico qual o valor de resistência necessário.

Portanto, embora, em princípio, essas máquinas possam decidir qualquer idioma, elas não violam Church-Turing porque não podem ser fisicamente construídas.

Você pode se envolver em um advogado de regras e alegar que alguém poderia lhe entregar uma dessas máquinas e dizer: "Ei, olha, essa máquina tem exatamente os valores de resistência corretos para resolver o problema de parada!" No entanto, eles não têm como provar essa afirmação, pois não podem medir os componentes com precisão infinita; portanto, o melhor que podem reivindicar com justificativa é "Eu testei isso em algum conjunto finito de entradas e ele decidiu corretamente o problema essas entradas ". Bem, qualquer subconjunto finito do problema de parada já é decidido por Turing, então isso não é nada empolgante.