Berächebarkeit

In dr Berächebarkeitstheorii sait men von ere Funktion si siig berächebar, wenn es en Algorithmus git, wo die Funktion berächnet. D Funktion, won en Algorithmus berächnet, isch definiert dur d Usgob (Output), wo dr Algorithmus drmit uf en Iigob (Input) reagiert. D Funktion isch definiert über dr Mängi vo 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 eme Berä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 dr Turingmaschine, d. h. si si Turing-mächtig. D Church-Turing-These behauptet 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 d Loop-Programm. Die chönne zum Bispil d Ackermann-Funktion, wo Turing-berächebar isch, nit berächne.

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

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