Recursion and subrecursion over finite and infinite words with applications to computable real valued functions [Elektronische Ressource] / von Holger Schulz

Recursion and Subrecursion overFinite and Infinite Words withApplications toComputable Real Valued FunctionsDissertationzur Erlangung des Grades eines Doktorsder Naturwissenschaftenvorgelegt vonHolger Schulzgeb. am 1969-06-14 in Langenhageneingereicht beim Fachbereich 6 · Mathematikder Universität SiegenSiegen 2006Dekan: Prof. Dr. Wolgang Hein1. Gutachter: Prof. Dr. Dieter Spreen2.hter: Prof. Dr. Vasco BrattkaDatum der mündlichen Prüfung: 2006-06-263AcknowledgementFirst of all I have to thank Professor Dieter Spreen for enabling me to write this thesis. Thiswork would not have been possible without his support and advice. I owe him a lot.Special thanks go to Professor Vasco Brattka for kindly accepting to referee this thesis.Further all my colleagues must not stay unmentioned. I still like the working environmentthey provide.45AbstractA recursion scheme for functions on intervals to approximate real-valued functions is de-scribed and compared with recursion schemes on finite and infinite words.ZusammenfassungEs wird ein Rekursionschema für Funktionen auf Intervallen, die reellwertige Funktionenapproximieren, beschrieben und mit Rekursionsschemata auf endlichen und unendlichenWörtern verglichen.6Contents1 Introduction 92 Preliminaries 132.1 Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Primitive Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.