01
Hesaplama Modelleri
Sonlu otomatların tanıyabildiği diller, üretim kurallarının aştığı sınır, evrensel model ve adım bütçesinin karar verilemezlik karşısındaki yetersizliği.
- 01 Sonlu Otomatlar Durum bütçesinin tam sayımla ölçülmesi: 31 dizilik evrende 1 durumlu otomatlar 2, 2 durumlu 26, 3 durumlu 1054 ayrı dil tanıyor; evrende yazılabilecek 2 üzeri 31 dilin yanında bu, 0,0000004908'lik bir paydır.
- 02 Bağlamdan Bağımsız Diller Durum bütçesinin yetmediği dillerin ölçülmesi: eşit sayıda a ve b dizisi için gereken durum sayısı uzunluk sınırıyla 3, 5, 7, 9, 11 diye büyürken tek satırlık bir üretim kuralı aynı dili tam olarak üretiyor ve kuralın betimi hiç büyümüyor.
- 03 Turing Makinesi Şeritli modelin tam sayımla ölçülmesi: 2 durumlu 2 simgeli 20.736 makinenin 9784'ü duruyor, en uzun duran koşum 6 adım ve bütçe 6'dan 200'e çıkarıldığında sayı hiç değişmiyor; durmayan 10.952 makinenin 5040'ı döngü kanıtıyla karara bağlanıyor.
- 04 Karar Verilemezlik Gözlemin kanıt olmadığının ölçülmesi: tek satırlık bir sayaç kuralında 1000 başlangıcın bütçe 5'te 7'si, 200'de 1000'i duruyor, ama aynı bütçe 5000 başlangıçlık evrende 9 tanesini karara bağlayamıyor ve her bütçeyi yanıltan bir başlangıç bulunabiliyor.