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ı: Belirtilmemiş.
Ö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
- Çok amaçlı karar verme metodları ve tekstil sanayiinde bir uygulama
Multiple criteria decision making methods and an application to the textile industry
H.EDA ÖZTÜRK
Yüksek Lisans
Türkçe
1992
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. RAMAZAN EVREN
- FDDI tabanlı bir ağ sistemi için etkin bir gerçek zamanlı iletişim yapısının tasarımı
Design of an efficient real time communication structure for an fddi based network system
FEZA BUZLUCA
Doktora
Türkçe
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
PROF. DR. EMRE HARMANCI
- Çelik halatlı titreşim sönümleyicilerin sonlu elemanlar metodu ile incelenmesi
Steel wire rope isolators analysis with the finite element method
MEHMET KUDUZOĞLU
Yüksek Lisans
Türkçe
2018
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. SERPİL KURT HABİBOĞLU
- Entegre fotonik cihazların tasarımına yönelik hesaplama tabanlı yaklaşımlar
Integrated photonic device designs based on computational approaches
EMRE BOR
Doktora
Türkçe
2020
Elektrik ve Elektronik MühendisliğiTobb Ekonomi ve Teknoloji ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. HAMZA KURT
DOÇ. DR. MIRBEK TURDUEV
- Constant-space, constant-randomness verifiers with arbitrarily small strong error
Sonlu hafıza ve sonlu rastgelelik kullanan, alabildiğine küçük katı tip hatalı doğrulayıcılar
MEHMET UTKAN GEZER
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. AHMET CELAL CEM SAY