Otomata Teorisi #01 | Hesaplamanın üç sorusu

Eğitmen: Dr. Süleyman Burak ÇELİK

Merhaba, Akedumi otomata teorisi ve biçimsel diller dersine hoş geldiniz. Önünüzde küçük bir denetim kaydı var. Her işaret ya sıfır ya da bir. Sorumuz şu: bu kayıtta en az bir uyarı var mı? Bir okuyucu bütün kaydı tarıyor, diğeri yeterli bilgiyi bulunca duruyor. İkisi aynı cevabı verebilirken farklı sayıda işaret inceleyebilir. Bu küçük farkla hesaplamanın üç temel sorusunu birbirinden ayıracağız. Özgün ikili uyarı tarayıcısında aynı girdiyi iki yöntemle inceliyoruz. Tam tarama bütün sembolleri okurken erken duran yöntem ilk tanıkta bitiyor. İki durumlu okuyucuda tanığı görmek ile yöntemin tamamlanmasını ayrı izliyor; aynı cevap için yapılan sembol incelemelerini karşılaştırıyoruz. Bu derste: 1. Önce problemin sınırı 2. İki durumlu okuyucu 3. Tam taramanın adımları 4. Cevap ne zaman kesinleşir? 5. Aynı karar, farklı durma kuralı 6. Ne saydığımızı açık tutalım 7. Her girdide erken kazanç yok 8. Boş girdi ve başta tanık 9. Deney ile genel gerekçe 10. Üç alanı aynı örnekte ayırmak Bölümler: 0:00 Hesaplamanın üç sorusu 1:22 Önce problemin sınırı 2:35 İki durumlu okuyucu 3:51 Tam taramanın adımları 5:03 Cevap ne zaman kesinleşir? 6:14 Aynı karar, farklı durma kuralı 7:29 Ne saydığımızı açık tutalım 8:48 Her girdide erken kazanç yok 10:03 Boş girdi ve başta tanık 11:20 Deney ile genel gerekçe 12:37 Üç alanı aynı örnekte ayırmak 13:51 Sıradaki adım: matematiksel dil Kaynak kitap: Michael Sipser, Introduction to the Theory of Computation, Third Edition; §0.1. Basılı 1–3 / fiziksel PDF 25–27. Kavram ve konu sırası kaynaktan izlenir; anlatım, çizimler ve ikili tarama örnekleri özgündür. TypeScript geçişleri bağımsız Python tanık-konumu kümeleriyle çapraz denetlenmiştir. Sonlu testler genel kanıt değildir; bu yöntemin her sonlu girdide bitmesi, ilerleyen imlecin girdi uzunluğuyla sınırlı olmasına dayanır. Sayaç yalnız sembol incelemelerini sayar; doğrulama, çizim, bellek ayırma ve geçen süre bu sayaca dahil değildir. Matematiksel model, hesaplanabilirlik sorusu ve kaynak maliyeti ayrı ele alınır. Sonuçlar genel karar verilebilirlik, problem alt sınırı, donanım hızı veya güvenlik iddiası değildir. Hedef kitle: bilgisayar mühendisliği ve kuramsal bilgisayar bilimine giriş öğrencileri.