Berächebarkeit

In drBerächebarkeitstheoriisait men von ereFunktionsi siigberächebar,wenn es enAlgorithmusgit, wo die Funktion berächnet. D Funktion, won en Algorithmus berächnet, isch definiert dur dUsgob(Output), wo dr Algorithmus drmit uf enIigob(Input) reagiert. D Funktion isch definiert über drMängivo de Iigobe, wo dr Algorithmus drfür überhaupt e Usgob produziert. Wenn dr Algorithmus nit terminiert, d. h. zu keim Resultat chunnt, denn lit d Iigob nit im Definitionsberiich vo dr Funktion.

Dr Algorithmusbegriff basiert uf emeBerächnigsmodäll.Verschidnigi Berächnungsmodäll si entwigglet worde, es het sich aber usegstellt, ass die sterkste drvo gliich stark si wie s Modäll vo drTuringmaschine,d. h. si siTuring-mächtig.DChurch-Turing-Thesebehauptet dorum, ass d Turingmaschine dr intuitivi Begriff vo dr Berächebarkeit wiidergän.

Zu de Berächnigsmodäll, wo schwecher si as Turingmaschine, ghöre under anderem dLoop-Programm.Die chönne zum Bispil dAckermann-Funktion,wo Turing-berächebar isch, nit berächne.

E Begriff, wo mit dr Berächebarkeit äng verwandt isch, isch dEntscheidbarkeit.E Deilmängi von ere Mängi (zum Bispil eformali Sprooch) heisst entscheidbar, wenn ihricharakteristischi Funktion(im Wäsentlige s Prädikat, wo drzue ghört) berächebar isch.

Dä Artikel basiert uff ere fräie Übersetzig vudere Versionvum Artikel „Berechenbarkeit“vu de dütsche Wikipedia. E Liste vu de Autore un Versione ischdoz finde.