Computability· 2026Q2
Transfinite Melodiler: Sonsuz Zaman Makineleri İçin Yeni Hesap Edilebilirlik Sonuçları
The strange world of transfinite melodies—Recognizability for weak and strong infinite time α-register machines
- 0atıf
- Q2SCImago
- 2026yıl
Kısa özet
Sonsuz zamanlı yazmaç makineleri (ITRM'ler) için transfinli sıralı sayılar üzerindeki hesap edilebilirliğin karakterizasyonunu yapan yeni sonuçlar, hesap edilebilir ve tanınabilir kümeler arasındaki ilişkinin sıralı sayıya bağlı olarak dramatik bir şekilde değiştiğini ortaya koyuyor.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- α-ITRM'ler kullanılarak tüm transfinli sıralı sayılar α için parametresiz olarak tanınabilir 'kayıp melodiler' tanımlar.
- α-ITRM'ler ile tekrarlanan tanınabilirliğin çoğu α için L ve V arasında mutlak olduğunu gösterir.
- α-ITRM'ler için 'hepsi ya da hiçbiri' olgusunu α'nın uygun bir sınıfına geneller.
- α-wITRM'ler için kayıp melodilerin var olduğu sıralı sayıları α tam olarak karakterize eder.
- Boş veya hesap edilebilir kümelerden ayrık kümeler dahil olmak üzere, α-wITRM'ler için hesap edilebilir ve tanınabilir kümeler arasındaki oldukça değişken ilişkileri gösterir.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
For exponentially closed ordinals α , we consider recognizability of constructible subsets of α for α -(w)ITRMs and their distribution in the constructible hierarchy. In particular, for α -ITRMs, we show that there are lost melodies that are recognizable without parameters for all α and that iterated recognizability is absolute between L and V for most values of α ; moreover, we generalize the “all or nothing”-phenomenon that was hitherto known only for the case α = ω to a proper class of α . For α -wITRMs, we offer a complete characterization of those α for which lost melodies exist and show that the relation between the sets of computable and recognizable subsets of α varies wildly, depending on α : The computable sets may be included among the recognizable sets (which is usually the case in ordinal computability), but there are also class many values of α for which the set of recognizable sets is empty and others for which the set of recognizable sets is non-empty, but disjoint from the set of computable sets. This paper is an extension of our paper in the CiE 2023 proceedings.
Yazarların özeti; kaynağından alınmıştır. Computability, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science