Programlamada Turing Makinesi Tasarlama  – Programlama Nedir? – Programlama Bölümü – Programlama Yaptırma – Programlama Ödevleri – Programlama Ücretleri

 Turing Makinesi Tasarlama

Bunun için birkaç program yazana kadar bir sanal makineyi anlamazsınız. Bu alıştırmada Turing makinelerini anlamaya çalışıyoruz. Bir Turing makinesini belirtmenin doğrudan bir yolu bir geçiş tablosudur. Sütunlar eski durum, eski sembol, yeni sembol, yeni durum ve harekettir; burada L sola git, R sağa git ve H dur anlamına gelir. Başlangıç ​​durumu s ve durma durumu h’dir.

Örneğin, tek bir 1 dizisi dışında yalnızca 0’ları içeren bir bant verildiğinde, gerekirse sağdaki ilk 0’ın üzerine 1 ile yazarak sayıyı eşit uzunlukta yapabiliriz. Bir Turing makinesi bunu, en soldaki 1’den başlayıp daha sonra sağa hareket ederek, 1’lerin çalışmasının o kadar çift mi yoksa tek mi olduğunu takip etmek için iki durum arasında geçiş yaparak yapabilir.

Bant üzerinde 1 sembolü her geçtiğinde makine s ve b durumları arasında geçiş yapar. Böylece, s çift parite durumudur ve b tek parite durumudur. 0 bulunduğunda uygun sembol yazılır ve makine durur. Bant sembolü değişmese bile, tablodaki girişi açık bir şekilde doldururuz.

Sonlu bir dizide basit bir Turing makinesi simülatörü yazmak oldukça kolaydır ve bu alıştırmalara yardımcı olması için bunu yapmanız önerilir.

Turing makinesinin durumu, işlemci için fazladan bir sembol olan T ile tek bir sonlu bant sembolleri dizisi olarak temsil edilmesi kolaydır; her iki uçtaki son karakterin süresiz olarak tekrarlandığını varsayıyoruz. Dolayısıyla, 00001T000, tek bir 1 dışında 0’larla dolu bir bandı temsil eder ve Turing kafası şu anda tek 1’i içeren hücrede bulunur.

Sayıları temsil eden tally sistemi, 1’i 1 ve 2’yi 11 ve 3’ü 111 vb. olarak temsil etmek anlamına gelir, her iki tarafta da 0’larla isteğe bağlı bir dolgu miktarı ile 0111000 ayrıca 3’ü temsil eder.

1. Toplama 4+2’yi tally sisteminde T’nin Turing kafasının başlangıç ​​konumunu temsil ettiği 0001111011T000 olarak yazıyoruz.
Yalnızca sola hareket eden ve bunu tek bir eşdeğer tally taban numarasına çeviren bir makine yazın.
2. İkili sistemde, bir 0 bulana kadar 1’i 0’a çevirerek sola hareket ederek bir sayıyı artırabiliriz. Böyle bir Turing makinesi yazın.
3. Bir ikili sayı üzerinde bir artan durumu tekrar tekrar kullanarak ve taksitli sayıyı azaltarak, taksiti ikiliye çeviren bir makine yazın.
4. İki sayıyı ikili olarak toplayan bir makine yazın. Bu sefer teybe üç sembol ekliyoruz, böylece ilk durum sss10010s101sss olabilir, burada s bir boşluk karakterini temsil eder. Bu durumda istenen çıktı, orijinal numaraların silindiği sss10111sss’dir.
5. Farklı Turing makineleri, başlangıçta boş bir bant gibi aynı girdiye farklı davranır. İki sembollü bir bant verildiğinde, Turing makinesi T durmadan önce kaç tane 1 yazacağını sorabiliriz (durduğunu varsayarsak). Belirli sayıda durumda yalnızca sonlu sayıda makine olduğundan, yazılabilecek maksimum 1 sayısı olmalıdır. 
6. Bir n-durumlu makinenin veya n-durumlu bir Meşgul Kunduz’un kaç tane 1 yazacağını belirlemek çok zordur ve sayı Akerman’ın fonksiyonu gibi hızla yükselir.

Turing makinesi
Turing makinesi Nedir
Turing Makinesi PDF
Turing makinesi ekşi
Turing makinesi Örnek sorular
Turing makinesi örnekleri
Turing makinesi konu anlatımı

Deterministik Olmayan Makineler

Bir mühendislik tanımına göre, bir makinenin durumu, makinenin gelecekteki davranışını belirleyen bazı bilgilerdir. Kesinlikle, her durum makinesinin deterministik olması totologdur. Başka hiçbir makinenin durumu yoktur. Evrenin bir bütün olarak bir durumu olup olmadığı bilinmemektedir. Ancak bir durum mevcut olsa bile, çoğu zaman sadece bir kısmı ölçülebilir. Gerisi gizli. Yalnızca ölçülebilir kısmı gözlemlemek, her (gözlenebilir) durum için birden fazla olası geleceğin olabileceği anlamına gelir.

Ayrık bir deterministik makine için, her durum benzersiz bir sonraki duruma yol açar. Sonraki durum, mevcut durumun bir fonksiyonudur. Böyle bir makine, bir sonraki durum fonksiyonu ile donatılmış bir durum uzayı ile karakterize edilir. Bir sonraki durum ilişkisi ile deterministik olmayan ayrık bir makineyi tanımlamak doğaldır. Her eyaletin bir sonraki eyalet koleksiyonu vardır.

Makinenin içinde olabileceği (gözlemlenebilir) durumların bir koleksiyonu verildiğinde, bir sonraki durumda olabileceği durumlar kümesi, koleksiyondaki her bir durum için kümelerin birleşimidir. Bu nedenle, deterministik olmayan bir makine, orijinal makinenin durumlarının güç setinde deterministik bir makinenin özel bir durumudur. Deterministik olmayan makine tarafından döndürülen son değer, sonlandırmak için ilk deterministik makine tarafından döndürülen değerdir. Tabii ki, genel olarak, bu bir değerler topluluğudur.

Sonlu bir makinenin durumlarının güç seti de sonludur. Yani, deterministik olmayan bir sonlu makine, sadece daha büyük bir durum uzayında, hala sonlu bir makinedir. Bununla birlikte, deterministik olmayan bir makine olarak görülen sonlu bir makinenin tasarlanması veya değiştirilmesi, deterministik olarak görüldüğünden daha kolay olabilir. Deterministik olmayan makine, doğrudan paralel uygulamaya izin veren özel bir yapıya sahiptir.

Turing makineleri için makine durumu, bandın durumu ile birlikte işlemcinin durumu ve konumudur. Bu, sonlu bir tamsayı olarak kodlanabilir. Turing makinesi sayılabilir bir durum makinesidir. Sayılabilir durum uzayının alt kümeleri sayılamaz, bu da bizi modern masaüstü bilgisayarın kapsamının tamamen dışına çıkarır. Bu nedenle, alt kümeler sonlu olacak şekilde sınırlandırılacaktır. Sayılabilir bir durum uzayının sonlu altkümeleri kümesi de sayılabilirdir.

Deterministik olmayan bir Turing makinesinin deterministik bir makine tarafından taklit edilebileceği doğrudur, ancak hemen net değildir. Hanoi dizisini kullanarak, sayılabilir sayıda sanal bandı tek bir bantta birleştirebiliriz. Karalama alanı için kullanılan bir sanal bantla, deterministik bir Turing makinesi, deterministik olmayan bir Turing makinesini simüle edebilir.

Gerçek deterministik olmayan makine, deterministik makineden daha fazlasını hesaplayabilir, ancak asla ondan daha azını hesaplayamaz. Benzer şekilde, tipik olarak daha hızlıdır ama asla daha yavaş değildir. Bununla birlikte, bu hızlanma sadece zaman içinde kullanılabilir, çünkü ilgili deterministik makinelerin her birinin adımlarını gerçekten saymamız gerekir.

“legendhomework” Turing makinesi,Turing makinesi Nedir,Turing Makinesi PDF,Turing makinesi ekşi,Turing makinesi Örnek sorular,Turing makinesi örnekleri,Turing makinesi konu anlatımı alanlarında hizmet vermektedir.

Makale Deniz

Biyografinin Tamamını Gör