Infinite time turing machines with finite space

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümü, Türkiye

Tezin Onay Tarihi: 2025

Tezin Dili: İngilizce

Öğrenci: YEKTA SADEGHI AVAL

Danışman: Burak Kaya

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

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