Teza Churcha-Turinga i moc obliczeniowa sieci neuronowych

29

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?

John R. L.
źródło

Odpowiedzi:

46

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.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ć).R

Luke Mathieson
źródło
5
+1 przynajmniej częściowo dla końcowej gry słów!
Omar,
2
Interesujące jest dla mnie, że wydaje się, że jest to związane z pytaniem, czy Wszechświat jest cyfrowy, oraz innymi zagadnieniami mechaniki kwantowej, takimi jak podstawowa niepewność systemu.
Wszechobecny 12.12.17
7
R
1
Wydaje mi się, że gra słów naprawdę dodaje coś do tej odpowiedzi, ponieważ jest to tak powszechne naiwne nieporozumienie, że prawdziwe liczby są prawdziwe.
R ..
25

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. 2Ω

  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.

David Richerby
źródło