Teza Churcha-Turinga i moc obliczeniowa sieci neuronowych

Teza Church-Turinga stwierdza, że ​​wszystko, co można fizycznie obliczyć, można obliczyć na maszynie Turinga. Artykuł „Obliczenia analogowe przez sieci neuronowe” (Siegelmannn i Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) twierdzi, że sieć neuronowa o określonej formie (ustawienia są przedstawione w artykule) jest silniejsza. Autorzy twierdzą, że w czasie wykładniczym ich model może rozpoznawać języki, których nie można obliczyć w modelu maszyny Turinga.

Czy nie jest to sprzeczne z tezą Turinga?

Nie, nadal jest zgodny z tezą Churcha-Turinga, ich model jest wyposażony w prawdziwe liczby rzeczywiste (jak w dowolnych elementach ), które niemal natychmiast rozszerzają moc poza moc maszyny Turinga. W rzeczywistości tytuł 1.2.2 brzmi „Znaczenie (nieobliczalnej) rzeczywistej wagi”, gdzie dyskutują, dlaczego ich model został zbudowany w taki sposób, aby zawierał komponenty nieobliczalne.$\mathbb{R}$

W rzeczywistości istnieje wiele modeli obliczeń, które przekraczają moc maszyn Turinga (qv Hypercomputation ). Chodzi o to, że żadnego z nich najwyraźniej nie da się zbudować w świecie rzeczywistym (ale może w świecie - przepraszam, nie mogłem się oprzeć).$\mathbb{R}$

Aby nieco rozwinąć odpowiedź Luke'a , fizyczne zbudowanie sieci neuronowej w celu rozwiązania dowolnego języka wymaga wytworzenia elementów elektronicznych o nieskończenie precyzyjnych oporach i tak dalej. Nie jest to możliwe na wiele sposobów:

1. $\mathrm{2\,\Omega}$

2. Zmiany rezystancji wraz z temperaturą i prądem przepływającym przez rezystor zmienią jego temperaturę.

3. Zakładając nawet, że znasz inżyniera elektronicznego / czarnoksiężnika, który może wytwarzać rezystory o dowolnej wybranej wartości i które nie zmieniają rezystancji wraz z temperaturą, skonfigurowanie maszyny do decydowania o języku nieobliczalnym będzie wymagało obliczalnych wartości rezystancji. Więc nie ma sposobu, abyś rzeczywiście powiedział elektronicznemu inżynierowi / czarownikowi, jakiej wartości oporu potrzebujesz.

Tak więc, chociaż w zasadzie maszyny te mogą decydować o dowolnym języku, nie naruszają Kościoła Turinga, ponieważ nie można ich fizycznie zbudować.

Możesz zaangażować się w przestrzeganie zasad i twierdzić, że ktoś może podarować ci jedną z tych maszyn i powiedzieć: „Hej, spójrz, ta maszyna ma akurat dokładnie odpowiednie wartości oporu, aby rozwiązać problem zatrzymania!” Nie mają jednak możliwości udowodnienia tego twierdzenia, ponieważ nie mogą zmierzyć składników z nieskończoną precyzją, więc najlepszym, co mogą uzasadnić, jest „przetestowałem to na pewnym skończonym zestawie danych wejściowych i poprawnie zdecydowałem o problemie zatrzymania na te dane wejściowe ”. Cóż, każdy skończony podzbiór problemu zatrzymania jest już rozstrzygalny przez Turinga, więc nie jest to nic ekscytującego.