EIR'E NEUE DEFINITION BERECHENBARER REELLER FLTNKTIONES von JURGEN HAUCK in Berlin (DDR)
Einleitung
Im Jahre 1936 begannen BANACH und MAZUR ihre Untersuchungen auf dern Grbiet der Konstruktiven Analysis. Sie nennen eine reelle Funktion berechenbar, fa 11s sie beziiglich berechenbarer reeller Folgen invariant ist. Weitere Definitionen stainmen von SPECKER (1949), MARKOW (1954), GOODSTEIN (1957) und LACOMBE (1958). Einen grundsiitzlich anderen Weg als seine Vorgitnger schliigt GRZEQORCZYK ein. Er definiert zuniichst induktiv allgemein-rekursive Funktionale r. Eine reelle Funktion f IieiDt nun berechenbar, falls es ein allgemein-rekursives Funktional r gibt, so daD fur alle reellen Zahlen x und alle ganzzahligen Funktionen y gilt :
(1)
fur alle n KLAUA ( 1956) gibt eine ithnliche Definition, verwendet aber (potentiell) partiell-rrkursive Funktionale. SchlieDlich hat 1971 Verfasser die Definitionen yon GRZEGORCZYK und. KLAUA verallgemeinert. Dazu wurde zunachst der Begriff der Codierung bzw. Darstellung D eingefiihrt und dann eine Funktion f beziiglich der Darstellungeii D und D' berechenbar genannt, falls fiir jedes 5 aus jeder D-Darstellung y von x eine D'-Darstellung y' von fx konstruiert werden kann. Die Urnwandlung von y in y' mu13 dabei durch eine Turing-Maschine (partiell-rekursives Funktional) durchgefuhrt u-ertlen. Eine weitere Moglichkeit, berechenbare reelle Funktionen zu definieren, hieten metrische bzw. topologische Raume mit rekursiver Basis (siehe [4]). Ein Ohjekt a eines solchen Raurnes heiDt berechenbar, falls es rnit Elernenten der rekursiven Basis rnit beliebiger Genauigkeit -in bezug auf die betrachtete Metrik bzw. Topologieangeniihcrt werden kann. Es sei z. B. 2, die Menge der finiten !lkeppenfunktionen (siehe Abschnitt 1) und @(TI 8) = inf (Tz -~5'zt.J und ( T i , e ) die Vervollstiindigung von (2, , e). Dann ist (Xi, Zl, e ) ein rnetrischer Raurn rnit rekursiver Basis. I n cliesem Raum heifit f berechenbar, falls es eine rekursive Folge von Treppenfunktionen T, gibt mit (2)
If. -T,z( < lo-" fiir jedes z ~( 0 , 1) und jedes n. Die Grundidee der neuen Definition besteht nun darin, da13 wir (2) nicht fiir das gesamte Interval1 (0, 1) fordern, sondern eine Ausnahme endlich vieler Intervalle dcr Gesamtliinge kleiner als lo-" zulassen.
1. Fast berechenbare Funktionen
Untcr oinor finite,+> T'rcppnfunbtion in ( 0 , l} rorrrtehon wir oino nuf (0, l} dofiilicrto Furktion, die IIUI' eridlioh viele ratioriale Werk 1 amiiiiimt uiid dererl Urbildbwriche eines Funktionswertes aus endlich vielen links abgeschlossenen und rechts offenen bzw. abgeschlossenen Intervallen rnit rationalen Randpunkten T , s zusammengesetzt sind. 17.