Church Turing These :

broad part of [[112.00_anchor_overview]]

Geschichtlicher Background:

ungefähr zu den 1930er Jahren:

  • Turing hat die Turingmaschine erfunden / gefunden / bewiesen
  • Church findet / erfindet das -Kalkül
  • Gödel (und weitere) definierten anschließend rekursive Funktionen

Innerhalb weniger Jahre hatte man dann bewiesen, dass alle drei Modelle äquivalent (im Sinne der Berechenbarkeit) sind. Dies hat man anschließend durch eine gewisse Hypothese beschrieben:

Hypothese :

Alles was inituitiv berechnet werden kann, kann auch von einer Turingmaschine berechnet werden. Also wir können irgendein Problem, was man berechnen kann, wird auch mit einer Turingmaschine berechenbar sein, weil sie ja auch alles kann, was man berechnen kann. Weiter folgt mit dieser Hypothese: Jede “effektive berechenbare” Funktion kann von einer TM berechnet werden alternative Formulierung: Jeder Algorithmus kann mit Hilfe einer Turingmaschine implementiert werden. oder auch:Every finite physical system can be simulated to any specified degree on a universal turing machine

Hypothesen sind keine Tatsachen: Bedenke, dass die Church-Turing-These einer Hypothese entspricht und somit keiner Tatsache entspricht. Es kann sich theoretisch in naher Zukunft ändern, aber das kann auch nicht sein xd.

Andere “klassische” Berechnungsmodelle:

Das Streben bestand, dass man weitere Berechnungsmodelle findet, die eventuell mächtiger sind, als die obigen drei. Man hat sie leider nicht wirklich gefunden, meist sind die Berechnungsmodell am Ende gleich den obigen gewesen!

Betrachtung physikalischer Grenzen:

Was genau sind die physikalischen Grenzen der Berechenbarkeit - was kann man denn prinzipiell bauen? Diverse Intuitionen wären:

  • kann man physikalisch etwas bauen, was unendlich viel pro Sekunde berechnet? Nein
  • kann man N viele Operationen in gegebener Zeit bauen -> gewissermaßen schon, ja.

Quantencomputer sind Turing-äquivalent:

Jeder Quantencomputer kann durch einen normalen Computer simuliert werden - halt mit exponential mehr Zeit lol. Wenn die Rechenzeit aber nicht das Kriterium ist, dann sind beide Modelle doch äquivalent.

Gezeigt wurde das beispielsweise von: David Deutsch (1985). [[211.04_QuantumTheory_ChurchThesis.pdf]]

es gibt auch physikalische Modelle:

etwa Hypercomputing - also accelerating machines, relativistic machines. - also Modelle die formal mächtiger sein sollten als eine TM, aber man muss sich weiter die Frage stellen, ob man sie auch wirklich bauen kann siehe hier

künstliche Intelligenz besser / mächtiger ?

sind Neuronale Netze turing äquivalent?

Dafür gibt es diverse Paper, die diverse Ansätze betrachten und so unter Umständen turing completeness zu zeigen. Beispiele dazu [[211.02_AttentionIsTuringComplete.pdf]] oder [[211.06_TuringCompletenessOfModernNNArch.pdf]]

Oft hängen die Betrachtung sehr von den betrachteten Modellen und ihren Parametern ab, also komtt es ein wenig auf die Betrachtung an!

Diskussionen um die These :

Es gibt nach wie vor viele Diskussionen über die Church-Turing-These:

  1. Manche Argumente sagen, dass Funktionen und Strings ein eingeschränktes - zu sehr auf mathematik gestütztes/ fokussieres - Verständnis von Berechnungen entspricht. –> vielleicht sollte man den Scope verlassen, um mehr Einsicht zu erhalten?

  2. Manche sagen, dass das traditionelle Konzept eines Algorithmus zu eingeschränkt ist. –> im Kontext von machine Learning ist ein Algorithmus nicht mehr statisch, denn sein Modell und der Algorithmus hängt dann von Trainingsdaten ab!

Einschätzung von Dr Ulrike Luxburg:

Ich würde nicht darauf wetten, dass alles, was sich derzeit im Gebiet der kI tut, sich auf eine Turing-Berechenbarkeit zurückführen lässt. vielleicht ist es auch gar keine so interessante Frage. Bzw haben wir damit eine falsche Frage gestellt, weil wir auf was anderes abzielen möchten?

Die offentsichtliche Frage am Horizont könnte sein. gibt es denn eine künstliche Intelligenz? - Physikalische kann nichts dagegen sprechen, zumindest wenn wir herausfinden, wieso Menschen intelligent sind –> man kann die Struktur eines Menschen irgendwann vielleicht simulieren -> macht man ja schon mit neuronalen Netzen, die sich etwas daran orientieren.