Was bedeutet "turingmächtig"?

1 Antwort

Du suchst vermutlich Turing-Vollständig. Turingmächtig bedeutet anscheinend das selbe.

Eine Programmiersprache ist Turing-Vollständig/Turingmächtig, wenn jede Operation einer Turing-Maschine durch die Programmiersprache nachgebildet werden kann und wenn jede Operation der Programmiersprache durch eine Turing-Maschine nachgebildet werden kann.

In der Regel ist das aber unmöglich, da Turing-Maschinen unendlich groß sein können. Darum wird Turing-Vollständigkeit/Turingmächtigkeit auch dann angenommen, wenn die Programmiersprache mit unendlich viel Speicher diese Emulation schaffen könnte.

Wenn es dich interessiert, lies von Alan Turing "On Computable Numbers, with an Application to the Entscheidungsproblem". Harter Tobak für Informatiker.

Was möchtest Du wissen?