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: University of Leeds
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 92
Ö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
- Öğ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ğitim Yönetimi ve Politikası Ana Bilim Dalı
PROF. DR. ALİ BALCI
- Öğretmen algılarına göre değişim yorgunluğunun çeşitli değişkenler açısından incelenmesi (Akçakoca örneği)
Exchange faciliation according to teacher's perceptionsinvestigation in terms of various variables (Akcakoca example)
ÇİĞDEM ŞAHİN
Yüksek Lisans
Türkçe
2021
Eğitim ve ÖğretimDüzce ÜniversitesiToplam Kalite Yönetimi Ana Bilim Dalı
PROF. DR. ENGİN ASLANARGUN
- 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
- Vardiyalı çalışan acil servis hemşirelerinin sağlık durumlarının ve bunları etkileyen etmenlerin incelenmesi
Investigation of the health status of emergency nurses working in shift and the factors affecting them
ABDULKADİR MERCAN
Yüksek Lisans
Türkçe
2023
Hemşirelikİzmir Katip Çelebi ÜniversitesiHemşirelik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ DENİZ ŞANLI