KA RADO-Funktion

RADO-Funktion

Die Rado-Funktion ("Busy Beaver") \Sigma : \N \rightarrow \N ermittelt die größtmögliche Anzahl an Einsen, die von einer stoppenden Turing-Maschine mit n Zuständen auf ein anfangs leeres Band geschrieben werden. Dabei spielt es keine Rolle, an welcher Position die Einsen stehen, das heißt sie können auch durch Leerstellen unterbrochen sein. Ebenso spielt es keine Rolle, an welcher Stelle der Kopf der Turing-Maschine zum stehen kommt.

Funktionswerte:

Nachweis der Nichtberechenbarkeit