Infinite time turing machines with finite space
Sonlu belleğe sahip sonsuz zamanli turing makineleri
- Tez No: 960890
- Danışmanlar: DR. ÖĞR. ÜYESİ BURAK KAYA, DOÇ. DR. AHMET ÇEVİK
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 52
Özet
Hamkins ve Lewis tarafından tanıtılan sonsuz zamanlı Turing makineleri (ITTM'ler), klasik hesaplamayı sonsuz ordinal zamana genişletir. Bu tezde, bellek kısıtlamalarına sahip ITTM'leri çalışacağız. Standart ITTM'ler ve bazı çeşitleri hakkında temel sonuçları sunduktan sonra, sonlu hesapsal bellek kullanan ITTM'lerin durma davranışlarını inceleyeceğiz. Daha özel olarak, Defrain, Durand ve Lafitte'in böyle bir ITTM'nin durma zamanının ω^ω'yı geçemeyeceği sonucunu daha detaylı bir analizle ve kısmen farklı kanıtlarla tekrar inceleyeceğiz. Ayrıca, genel durma zamanı ω^ω olan ve sonlu hesapsal bellek kullanan bir ITTM inşa ediyoruz. Sonuçlarımız, her girdideki bellek kısıtlamasının durma zamanını nasıl etkilediğini göstermektedir.
Özet (Çeviri)
Infinite time Turing machines (ITTMs), introduced by Hamkins and Lewis, extend classical computation into transfinite ordinal time. In this thesis, we study ITTMs with space restrictions. After presenting fundamental results about standard ITTMs and some of its variants, we investigate the halting behavior of ITTMs that use finite computational space. In particular, we revisit the result of Defrain, Durand and Lafitte that the halting time of such an ITTM cannot exceed ω^ω on each input, with a more detailed analysis and slightly different proofs. We also construct an ITTM that uses finite computational space whose overall halting time is ω^ω. Our results demonstrate how the space restriction on each input affects the halting time.
Benzer Tezler
- Atölyede iş çizelgeme
Operations scheduling in job shops
GÖKHAN KIPÇAK
Yüksek Lisans
Türkçe
1990
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ATAÇ SOYSAL
- A hypercomputational approach to the agent causation theory of free will
Özgür iradenin özne nedensellik teorisine hiperbilişimsel bir yaklaşım
SERHAN MERSİN
Yüksek Lisans
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilişsel Bilim Ana Bilim Dalı
DOÇ.DR. ERDİNÇ SAYAN
Y.DOÇ.DR. BİLGE SAY
- Frezeyle tornalama operasyonunun geometrik, kuvvet ve ısıl modellenmesi
Geometric, force and thermal modeling of turn-milling operations
UMUT KARAGÜZEL
Doktora
Türkçe
2016
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA BAKKAL
PROF. DR. ERHAN BUDAK
- Gödel makinelerinde öğrenme sorunu
Learning problem in Gödel machines
ABDULLAH HANZALE KORKMAZ
Yüksek Lisans
Türkçe
2024
Felsefeİstanbul ÜniversitesiSistematik Felsefe ve Mantık Ana Bilim Dalı
PROF. DR. ÖZGÜÇ GÜVEN
- Türkiye popüler müziğinin yeni alanı: Dijital kültür endüstrisi
The new space of popular music in Turkey: Digital culture industry
ONUR KARABİBER
Doktora
Türkçe
2023
Müzikİstanbul Teknik ÜniversitesiMüzikoloji ve Müzik Teorisi Ana Bilim Dalı
PROF. SONGÜL KARAHASANOĞLU