Turingmaschine

Wie me sich e Turingmaschine cha vorstelle: E Band mit Informatione und e Schriib-Läs-Chopf

D Turingmaschine isch e Modäll, wo dr britisch Mathematiker Alan Turing 1936 entwigglet het, für zum e Klass vo berächebare Funktione zu bilde. S ghört zu de grundlegende Konzept vo dr Informatik.

Dr Turing het s Modäll im Rahme vom Hilbertprogramm zur Lösig vom so genannte Entscheidigsproblem, wo dr David Hilbert im Johr 1920 formuliert het, in dr Schrift "On Computable Numbers, with an Application to the Entscheidungsproblem" vorgstellt. Si Absicht isch gsi mit dr Turingmaschine e Modäll z mache vom mathematisch schaffende Mensch.

S Bsundrige an ere Turingmaschine isch, ass si mit nume drei Operatione (Läse, Schriibe und Schriib-Läs-Chopf bewege) alli Broblem cha löse, wo au vom ene Computer chönne glöst wärde. Sämtligi mathematischi Grundfunktione wie Addition und Multiplikation löön sech mit dene drei Operatione simuliere. Die drei eifache Operatione länge für zum komplexi Operatione vo de gängige Computerprogramm z simuliere. Ere Funktion, wo eso mit ere Turingmaschine cha berächnet wärde, sait me e turingberächebari Funktion.

D Church-Turing-These stellt d Behauptig uf, ass e Turingmaschine mathematischi Funktione cha löse wo vo Mensche berächebar si. Dodrus darf me aber nit schliesse, ass e Turingmaschine alli mathematische Funktione chönnt löse. So cha me öbbe anhand vom Stopproblem zeige, ass es mathematischi Funktione git, wo vo Turingmaschine (und dorum noch dr Church-Turing-These au vom Mensch) nit chönne berächnet wärde.

Dä Artikel basiert uff ere fräie Übersetzig vu dere Version vum Artikel „Turingmaschine“ vu de dütsche Wikipedia. E Liste vu de Autore un Versione isch do z finde.