Tibor Radó (* 2. Juni 1895 in Budapest, † 12. Dezember 1965 in New Smyrna Beach) war ein ungarischer Mathematiker.
Leben
Tibor Radó nahm an der Universität Budapest ein Ingenieurstudium auf, wurde jedoch nach Ausbruch des ersten Weltkriegs 1915 in die österreichisch-ungarische Armee eingezogen und geriet 1916 in russische Gefangenschaft. Erst 1920 konnte er nach Ungarn zurückkehren und seine Ausbildung mit einem Studium der Mathematik in Szeged fortsetzen. Dort promovierte er 1922 und arbeitete anschließend als Assistent und Privatdozent. 1928/1929 arbeitete er an Universitäten München und Leipzig. 1930 erhielt er einen Lehrstuhl für Mathematik an der Ohio State University, den er bis zu seiner Emeritierung im Jahr 1964 innehatte. Radó leistete wichtige Beiträge zur Variationsrechnung, Potentialtheorie, zu partiellen Differentialgleichungen, zur Differentialgeometrie und Topologie. Von ihm stammt die Idee der Busy Beaver-Funktion (1962) als Beispiel einer eindeutig als Algorithmus beschriebenen, aber nicht berechenbaren Funktion.
Busy Beaver
Radó ging folgender Frage nach: Wie viele Einsen kann eine Turingmaschine mit n Zuständen auf ein leeres Band schreiben, bevor sie schließlich anhält? Eine solche Turingmaschine wird "busy beaver" (fleißiger Biber) genannt. Die Busy-Beaver-Funktion bb(n) ist zwar wohldefiniert, aber schon für n > 4 ist der Wert bb(n) nicht bekannt. Rado konnte beweisen, dass es kein Verfahren gibt, das für beliebige n den Funktionswert bb(n) berechet, d.h. dass diese Funktion nicht berechenbar ist.
| Anzahl der Zustände n | Maximale Anzahl der Einsen bb(n) |
|---|---|
| 1 | 1 |
| 2 | 4 |
| 3 | 6 |
| 4 | 13 |
| 5 | ? |
Werke
- Über den Begriff der Riemannschen Fläche, Acta Mathematica (Szeged, 1925)
- The problem of least area and the problem of Plateau, Mathematische Zeitschrift 32/1930
- On the Problem of Plateau, Springer-Verlag (Berlin, 1933)
- On Non-Computable Functions, Bell System Technical Journal 41/1962
- Computer studies of Turing machine problems, Journal of the ACM 12/1965