Tiered arithmetic, its functional interpretation and slow growing bounds
Başlık çevirisi mevcut değil.
- Tez No: 400681
- Danışmanlar: PROF. S. S. WAINER
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2000
- Dil: İngilizce
- Üniversite: Unıversıty Of Leeds
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Özet yok.
Özet (Çeviri)
In 1992, Bellantoni and Cook developed a new recursion theoretic characterisation of the polytime functions, EC, in which it is shown that a natural two-sorted re-interpretation of the usual primitive recursion schemes characterises polynomially bounded computation over the binary representation of numbers. This thesis is based on Bellantoni-Cook's variable separation over unary notation. We first define a two-sorted Peano Arithmetic, PA(\), formulated with this variable separation, with quantification allowed only over one sort, output (safe) variables, and induction allowed only over the other sort, input (normal) variables. From PA(;) we obtained its two-sorted fragment Si-Induction, Si(;) ? IND, by restricting the induction rule to Xh(;)-formulas. We then get the result that the provably terminating functions of the S^;) ? IND turn out to be exactly the Grzegorczyk £2 functions, such functions being computable on a Turing Machine in Linear Space (bounded by a linear function of the length of its binary input). We develop the two-sorted higher type Godel primitive recursive functionals T(;) by applying this variable separation. We then get the result that every provably recursive function of two-soxted full PA{\) is characterised by the two-sorted Godel's Dialectica interpretation of arithmetic, and we show that every elementary function, in Grzegorczyk's class £3, is definable in T{\). We then prove that the converse of this result, that every definable function in T(;) is elementary, This is proved by using normalisation and transfinite counting by means of infinite terms. This work is related to other results of Buss, Bellantoni, Beckmann-Weiermann, Leivant and Ostrin but our context and methods are quite different. The bounding functions for the two-sorted theory are now the Slow Growing ones rather than the Fast Growing functions which bound computations in the usual single-sorted versions of Peano Arithmetic.
Benzer Tezler
- Kırşehir ilinde ana sınıflarında çalışan kadrosuz usta öğreticilerin kendi yeterliliklerine ait görüşlerinin incelenmesi
The examination ofthe unstaffed teachers? own ideas about their proficiencies who work in Kırşehir city kidergarden schools
FERHAT BAŞ
Yüksek Lisans
Türkçe
2006
Eğitim ve ÖğretimGazi ÜniversitesiOkul Öncesi Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. AYŞEGÜL SELİMHOCAOĞLU
- Spor merkezlerine devam eden bireylerin spordan ve spor merkezlerinden beklentilerinin karşılanma düzeyleri (Bursa ili örneği)
Level of expectation of sports and sports center expectations of individuals (Bursa province example)
MUSA ERDANLI
Yüksek Lisans
Türkçe
2021
SporBalıkesir ÜniversitesiBeden Eğitimi ve Spor Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ALİ NACİ ARIKAN
- Öğretmenlere göre kamu ve özel liselerde iş yaşamı kalitesi ve örgütsel bağlılıkla ilişkisi
Quality ofwork life and its relation to organizational commitment according to teachers in public and private secondary schools
MUSTAFA ERDEM
Doktora
Türkçe
2008
Eğitim ve ÖğretimAnkara ÜniversitesiEğitimin Yönetimi ve Politikası Ana Bilim Dalı
PROF. DR. ALİ BALCI
- Ameliyathane çalışanlarının cerrahi aletlerle yaralanma riski ve bunu etkileyen faktörlerin incelenmesi
The research of risk of surgical staff's injuries with surgical insruments in the operating room and factors which influence it
DİLEK KUTLU
Yüksek Lisans
Türkçe
2007
Halk SağlığıAfyon Kocatepe ÜniversitesiCerrahi Hastalıklar Hemşireliği Ana Bilim Dalı
DOÇ.DR. SEZGİN YILMAZ
- Büyükşehirlerde kentiçi ulaşım hizmetlerinin entegrasyonu ve yönetimi (İstanbul Metropoliten alanı için bir model önerisi)
The integration and administration of intra-city transportation services in metropolitian areas
AHMET FİDAN