Turingmaschine
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.

Informatik
Maschine