Mapping Reducibility (Haritalama İndirgenmesi)
İndirgeme
İndirgeme tanımı olarak bir problemi başka bir probleme dönüştürmek için hesaplanabilir fonksiyonların kullanılmasıdır.
Özellik 1.a:Herhangi bir A problemi, B problemine indirgenirse, o zaman herhangibir B çözümü A'nın bir çözümünü bulmak için kullanılabilir."Burada A yada B problemlerinin kendilerinin çözümü hakkındabir varsayım yoktur"
Örnek Problem 1.1 : "Malatya'dan İstanbul'a gitmek"
Çözüm 1.1:Burada ki problemi şu şekilde indirgemeler yapabiliriz
- Gitmek için uçak bileti almaya indirgeme
- Uçak bileti almak için paraya kazanmaya indirgeme
- Para kazanmak için işe girmeye indirgeme
Örnek Problem 1.1 için belirtilen çözüm de görüldüğü gibi bir problemini başka bir probleme indirgeyerek ana problemin çözümünde kullanabiliriz.
Eğer A problemi, B problemine indirgenebiliyorsa:
- A problemi B probleminden daha zor olamaz.
- A kararlı ise B de kararlıdır (decidable)
- A kararsız ise B de kararsızdır (undecidable)
İndirgenme tanımı yaptıktan sonra Mapping Reducibilty tanımını yapabilmek için bir kaç konuyu özet şeklinde değinilmesi gerekmektedir. Başlangıç olarak Turing Makinesi (Turing Machine) tanımı ve özelliklerini kısaca inceleyelim.
Turing Makinesi (Turing Machine)
Turing makinesi , karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılmasını sağlayan hesap makinesi.
Turing makinesi DFA (Deterministic Finite Automata) benzerdir ama DFA'dan farklı olarak sınırsız bellek görevi gören bir tape yapısı vardır. Sembolleri okuyup/yazabilen ve tape üzerinde hareket edebilen bir tape head'ı vardır.
Turing makinesinin DFA veya CFG(Context Free Gramer)'dan farkı olarak, input'un aslında bir bant üzerinde olmasıdır ve başlangıçta bant yalnızca input içerir ve diğer her yerde boştur. Turing Makine'si başladığında, geçiş işlevine göre durumlar (state), bant kafası (head) etrafında hareket edip ve bant üzerine değerler yazılır. Turing Makine'sinin herhangi bir anında kabul (accept) ya da red (reject) olduğunda makine tüm işlemleri durdurur.
Turing Makinesinin Genelleştirilmesi aşağıda ki gibi formalize edilir.
"Turing Makine'si genel olarak random-access memory (RAM) ve bir bilgisayar temsil eder."
Recognizable/Decidable Language
Bir dil L(M) , Turing Makine'si M/TM tarafından kabul edilebiliyorsa yada tanımlanabiliyorsa bu dil recognizable (tanımlanabilir) şeklinde ifade edilir.
Turing Makine'si DFA'yı simüle edebildiğinden dolayı, recognizable diller sezgisel olarak tüm Regular (R) (normal) dilleri ve Context Free Grammar (CFG) (bağlamdan bağımsız) dilleri içerir.
Verilen input için makine üç farklı durumda çalışır:
- Accept
- Reject
- Loop (Kabul etme veya reddetme durumuna geçmeden sonsuz döngü)
Makine sonsuz döngüye girebileceğinden dolayı bir girdi üzerinden işlemler sağlanırken makinin durup durmayacağı kesin olmayacağı için her zaman duran(halts) makineler tercih edilir. Bu türden loop olmayan makinelere "decider" adı verilmektedir.
"Bir M sınırlı adım da accept ya da reject durumuna geçiryor bu makineye decider adı verilir."
Bir decider bir dili tanımlayabiliyorsa (recognizable),o dil "decidable"'dir.
Co-Recognizable Language
Bir L dili ancak ve ancak (iff) tümleyeni L̅ (complement L) tanınabilirse veya başka bir deyişle L̅ için bir decider varsa co-recognizable'dir
Decidable Language
Bir kaç adımı ile örnek dillerin durumlarını inceleyelim.
Burada belirtilen ADFA eğer decidable ise B'nin w input'unu kabul edip etmediğinin durumunu test edilmesinin decidable olduğu belirtir.
Burada ADFA bir DFA problemini ifade eder bu probleminde B olduğunu ve w input ile durumunun test edilmesinin ya w input'unu kabul eder ya da ret ederek sonuç üretmesini doğrular bu şekilde decidable bir yapısı olur yani DFA hiçbir zaman w input'una karşı kararsız bir yapıda olmaz her zaman accept için bir son state(durum) vardır..
Burada EDFA herhangi bir boş DFA ifade eder ADFA gibi EDFA decidable'dır
(Burada A bir probleme EQ bir eşitliği E bir boşluğu ifade eder.)
Diğer durumlar için aşağıda ki belirtilenleri inceleyebilirsiniz.
Tablo 1.1
Teorem 1:Bir dil hem recognizable hem de co-recognizable isebu dil decidable'dir.
Yukarıda verilen dil için recognizable, co-recognizable ve decidable durumlarını belirliyelim.
Recognizable : Verilen w ∈ L ifadesi tanımlanabiliyor mu ? ("aaabbb" Evet)
Co-recognizable : Verilen w ∉ L ifadesi tanımlanabiliyor mu ? ("abbb" Evet)
Decidable : Verilen dil hem recognizable hem de co-recognizable olduğu için bu dil decidable 'dir
Turing Makine'sine değindikten sonra Mapping Reducibility tanımı yapmadan önce bir de Computable functions (hesaplanabilir fonksiyonlar) değinelim.
Computable Functions
Bir f: Σ*⟶Σ* fonksiyonu, eğer her input'da bir Turing Makinesi M/TM tape'inde sadece f(w) ile durursa (halt) hesaplanabilir bir fonksiyondur (Computable Functions).
"Hesaplanabilir fonksiyon her zaman herhangi bir input'ta durur. Varsayımsal olarak bilgisayardaki genel programa benzer."
Örnek olarak aritmetik operatörler (+-/*)
- Bir TM <m,n> inputlarını alıp, m+n sonucu üretiyor.
Mapping Reducibility
Mapping Reducibility, bir karar problemini başka bir karar problemine indirgemek için kullanılır.
Formalize Tanımı:
Bir A dili her w input'u için w ∈ A ⟺ f(w) ∈ B ifadesini sağlıyorsa A dili A ≤m B gösterimi ile B diline indirgenebilir.
Burada ki f fonksiyonu A'dan B'ye indirgenme olarak tanımlanabilir.
- w ∈ A → f(w) ∈ B
- f(w) ∈ B → w ∈ A ya da w ∉ A → f(w) ∉ B şartlarını sağlamak zorundadır.
Örnek olarak :
A = {x | x çift tamsayı}
B = {x | x tek tamsayı} bu ifadelere göre f(x) = x + 1 fonksiyonu A'dan B'ye bir indirgenmedir.
- A ≤m B
- A probleminin çözümü B probleminin çözümünden zor değildir.
- A ≤p B
- Herhangi bir B problemi çözülebiliyorsa A probleminde çözülebilir. (B ⇒ A)
Mapping Reducibility Özellikleri
Teorem 2 (Tümleyen Özelliği):A ve B için A ≤m B sağlanıyorsa A̅ ≤m B̅ ifadeside sağlanır. (A̅̅ = A)
Teorem 3 (Geçiş Özelliği):A ve B için A ≤m B ve B ≤m C sağlanıyorsa A ≤m C durumuda sağlanır.
Teorem 4 (Decidable Özelliği):A ve B için A ≤m B ve B decidable ise A'da decidable'dır aynı durum undecidable içinde geçerlidir.
Teorem 5 (Turing-Recognizable Özelliği):A ve B için A ≤m B ve B Turing-Recognizable ise A'da Turing-Recognizable'dır.Kanıt:B için MB recognizer tanımlarsak ve f ifadesini A'dan B'ye indirgeme fonksiyonu olarak ele alırsak;w input'u için MA :
- y=f(w) hesaplanır.
- MB(y) recognizer'ı çalıştırılır.
- Eğer MB accept ise MA accept'dir
- Eğer MB reject ise MA reject'dir
Burada görüldüğü gibi A ≤m B ifadesi ile B durumu w input'unu tanıyabiliyorsa A'da tanıyabilir.Ek Durum(Co-Recognizable Özelliği):Teorem 5'ün Kanıtın görüldüğü gibi w ∉ A durumunda Turing Makinesinin durumu belirsizdir o yüzden ATM co-recogizable değildir.w ∉ A input'u için MA :
- y=f(w) hesaplanır.
- MB(y) recognizer'ı çalıştırılır.
- MB reject ya da loop ise Ma reject ya da loop.
Teorem 6 (EQTM Turing-Recognizable Özelliği):Hatırlatma:EQTM={<A,B> | A ve B birer Turing Machine ve L(A) = L(B)}EQTM hem recognizable değildir hem de co-recognizable değildir.Kanıt:Hatırlatma:ATM={<M,w> | M bir Turing Machine ve w input'u kabul eder}<H> TM için bir decider olarak varsayalım <D> ise H kullanan başkabir TM olsun.O zaman <M> input'u için D çalıştıralım yani D : <M,<M>>
- H makinesini <M,<M>> ile çalıştır
- Eğer H için accept ise reject üret yada H için reject ise accept üret
Burada bir çelişki var bu yüzden ATM undecidable'dir.ATM undecidable olduğunu biliyoruz. O zaman ATM ≤m EQTM ve ATM ≤m E̅Q̅TMindirgenmesi için E̅Q̅TM ve EQTM ifadeleri hem recognizable hem de co-recognizable değildir.
Mapping Reducibility ne için kullanılır ?
- Undecidability ifadesini kanıtlamak için (Teorem 4)
- Non-Turing-Recognizable ifadesini kanıtlamak için (Teorem 5)
- Problem ya da durum indirgeme
Örnek Çözümler
Örnek Problem 1.2 :
Verilen A ve B NFA'ları için B ≤m A ifadesini sağlayan f(w) (Computable Functions) fonksiyonunu bulunuz
Çözüm 1.2:Verilen iki NFA için dilimizi oluşturursak:
- L(A) = {0n1n : n ≥ 0}
- L(B) = {00m1m : m ≥ 0}
O zaman w input A dili için;f(w)= 0w fonkisyonu A ≤m B durumunu sağlar.
ATM undecidable durumunu örnekle gösteriniz
Çözüm 1.3:Yukarıda state'ler ile belirtilen Turing Machine x/x,-> ifadesi ileçalışmaktadır. (read/write,go left/right) w=ncsu inputu ile TMçalıştırılır ise durumu belirsiz olur çünkü q1 durumunda loop oluşurbu yüzden ATM undecidable'dir.
Yorumlar
Yorum Gönder