Geri Dön

Tiered arithmetic, its functional interpretation and slow growing bounds

Başlık çevirisi mevcut değil.

PDF İndir

  1. Tez No: 400681
  2. Yazar: NAİM ÇAĞMAN
  3. Danışmanlar: PROF. S. S. WAINER
  4. Tez Türü: Doktora
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2000
  8. Dil: İngilizce
  9. Üniversite: University of Leeds
  10. Enstitü: Yurtdışı Enstitü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Tez No

    215267

    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

    Türkçe

    2006

    Eğitim ve ÖğretimGazi Üniversitesi

    Okul Öncesi Eğitimi Ana Bilim Dalı

    YRD. DOÇ. DR. AYŞEGÜL SELİMHOCAOĞLU

  2. Tez No

    235723

    Öğ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

    Türkçe

    2008

    Eğitim ve ÖğretimAnkara Üniversitesi

    Eğitim Yönetimi ve Politikası Ana Bilim Dalı

    PROF. DR. ALİ BALCI

  3. Tez No

    694742

    Öğ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

    Türkçe

    2021

    Eğitim ve ÖğretimDüzce Üniversitesi

    Toplam Kalite Yönetimi Ana Bilim Dalı

    PROF. DR. ENGİN ASLANARGUN

  4. Tez No

    668715

    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

    Türkçe

    2021

    SporBalıkesir Üniversitesi

    Beden Eğitimi ve Spor Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ALİ NACİ ARIKAN

  5. Tez No

    859424

    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

    Türkçe

    2023

    Hemşirelikİzmir Katip Çelebi Üniversitesi

    Hemşirelik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ DENİZ ŞANLI

Geri Dön