Otomata Teorisi #08 | İnşa, çelişki ve tümevarım

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

Önümüzde altı taşlık bir domino sırası var. İlk taşa dokunduğumuzda hareket komşuya, sonra onun komşusuna aktarılıyor. İlk itiş zinciri başlatıyor. Şimdi aynı düzeni hiç itmeden bırakalım. Taşların birbirine uygun uzaklıkta bulunması tek başına hareket üretmiyor. Bir başlangıç gerekli. Ekrandaki üç boyutlu düzen, birazdan kuracağımız matematiksel düşüncenin iki parçasını ayırmak için var. Altı taşlı Blender animasyonunda başlangıcın ve bağlantıların ayrı görevlerini görüyoruz. Çift sayıda düğüm için üç komşulu bir çizge kuruyor, kök üçün irrasyonelliğini kalan sınıflarıyla kanıtlıyor, bir yineleme bağıntısının formülünü taban ve keyfî adımla doğruluyoruz. Bu derste: 1. İddia hangi işi istiyor? 2. On düğümde üç komşu 3. Tarif neden her çift n için çalışır? 4. Geçici kabulü görünür tut 5. Kök üç bir kesir olsaydı 6. Üç kalan, tek zorunluluk 7. Keyfî adıma geçmek 8. İki katını al, üç ekle 9. Formülün genel adımı 10. İki parçadan biri eksikse Bölümler: 0:00 Bir başlangıç, bir geçiş 1:20 İddia hangi işi istiyor? 2:38 On düğümde üç komşu 3:57 Tarif neden her çift n için çalışır? 5:15 Geçici kabulü görünür tut 6:37 Kök üç bir kesir olsaydı 7:59 Üç kalan, tek zorunluluk 9:24 Keyfî adıma geçmek 10:46 İki katını al, üç ekle 12:09 Formülün genel adımı 13:35 İki parçadan biri eksikse 15:00 Kanıtın yükünü doğru taşı Kaynak kitap: Michael Sipser, Introduction to the Theory of Computation, Third Edition; §0.4 Types of proof. Basılı 21–25 / fiziksel PDF 45–49, §0.4 Types of proof; bölüm sonu alıştırmaları kapsam dışıdır. Konu sırası kaynaktan izlenir; anlatım, çizimler ve örnekler özgündür. Çift n ≥ 4 için çember ve karşıt eşleme üç ayrı komşu verir; on düğümlü örnekte 15 kenar ve 30 uç vardır. Kök üç için en sade m/n gösterimi yalnız geçici varsayımdır; üç kalan sınıfının kareleri 0,1,1 olduğundan pay ve paydanın ortak böleni 3 çıkar. Soyut x₀=4, xₜ₊₁=2xₜ+3 bağıntısının 7·2ᵗ−3 formülü taban ve keyfî indüksiyon adımıyla kanıtlanır. Yanlış başlangıç ve gecikmiş 3→4 kural hatası iki yükümlülüğün neden ayrı olduğunu gösterir. Sonlu domino animasyonu ve bağımsız TypeScript/Python uygulama kontrolleri genel matematiksel kanıtın yerine geçmez. Hedef kitle: bilgisayar mühendisliği ve kuramsal bilgisayar bilimine giriş öğrencileri.

Bu videoyu izlemek için Premium üyelik gerekir.