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?
źródło
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:
Zmiany rezystancji wraz z temperaturą i prądem przepływającym przez rezystor zmienią jego temperaturę.
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.
źródło