Durum
Adımlar
Banttaki semboller
Çalışma durumu

Durum Okunan Yazılan Hareket Sonraki durum

Turing makineleri hakkında daha fazla

Turing makinesi simülatörü

Turing makinesi mümkün olan en basit bilgisayardır: sonsuz bir bandın bir sembolünü okuyan, bir sembol yazan, bir hücre sola ya da sağa giden ve kısa bir kural tablosuna göre durumunu değiştiren bir kafa. Alan Turing onu 1936'da icat etti ve bilgisayarınızın yaptığı her şey ilke olarak bu şekilde yapılabilir. Kendi kurallarınızı yazın ya da bir örnek yükleyin, Çalıştır'a basın ve bandın adım adım değişmesini izleyin; altında tüm geçmişini gösteren bir diyagram bulunur. Bir program seçin ya da kendiniz yazın, girdiyi girin ve Çalıştır'a basın; kuralları birer birer izlemek için Adım'a basın, Geri bir adımı geri alır. Programın her satırı bir kuraldır: durum, okunan sembol, yazılacak sembol, hareket (L, R ya da hareketsiz için N) ve sonraki durum, örneğin A 0 -> 1 R B. Boş hücre için _ kullanın. Makine ilk kuralın durumunda, girdinin ilk sembolü üzerinde başlar ve H, accept ya da reject durumunda veya hiçbir kural uymadığında durur. Diyagram, her adımdan sonraki bandı yukarıdan aşağıya gösterir.

Nasıl çalışır

  1. Bir örnek program seçin ya da her satıra bir tane olmak üzere A 0 -> 1 R B gibi kurallar yazın ve girdiyi girin.
  2. Kafanın hareketini izlemek için Çalıştır'a, kuralları birer birer izlemek için Adım'a basın; Geri bir adımı geri alır.
  3. Durumu, adımları ve banttaki sembolleri kutucuklarda, bandın geçmişini ise diyagramda okuyun.

Makine nasıl çalışır

Makine her an birkaç durumdan birindedir ve kafası bandın bir hücresi üzerinde durur. O durum ve kafanın altındaki sembol için geçerli kural üç şey söyler: hücreye hangi sembolün yazılacağını, sola mı, sağa mı gidileceğini yoksa hiç hareket edilmeyeceğini ve sonra hangi duruma geçileceğini. Makinenin tamamı budur. H, accept ya da reject gibi bir durma durumuna ulaştığında ya da hiçbir kural uymadığında durur. İkili bir sayıya 1 ekleyen bir program bu türden yalnızca dokuz kurala ihtiyaç duyar.

Meşgul kunduzlar

Boş bir bantta başlatılan n durumlu makinelerden hangisi durmadan önce en çok 1 yazar? Bu soruyu 1962'de Tibor Radó sordu. Şampiyonlara meşgul kunduz denir ve bir bilgisayarın hesaplayabileceği her fonksiyondan daha hızlı büyürler. İki durum 6 adımda 4 tane 1, üç durum 6 tane 1, dört durum 107 adımda 13 tane 1 verir. 1989'da bulunan beş durumlu şampiyon 47.176.870 adımda 4.098 tane 1 yazar ve 2024'te çevrimiçi bir işbirliği, bilgisayarla doğrulanmış matematikle, duran başka hiçbir beş durumlu makinenin daha uzun çalışmadığını kanıtladı.

Sık sorulan sorular

Bir kuralı nasıl yazarım?

Her satıra bir kural: mevcut durum, okuduğu sembol, yazılacak sembol, hareket (L, R ya da N) ve sonraki durum, örneğin A 0 -> 1 R B. Ok ve virgüller isteğe bağlıdır. Boş hücre için _, yorum için # kullanın. Makine ilk kuralın durumunda başlar; H ya da halt adlı bir sonraki durum onu durdurur, accept ve reject ise onu bir kararla durdurur.

Bir Turing makinesi gerçekten her şeyi hesaplayabilir mi?

Yeterli bant ve zaman verildiğinde, herhangi bir bilgisayarın hesaplayabildiği her şeyi: buna Church–Turing tezi denir. Bir Turing makinesinin bellek sınırı yoktur, bu anlamda her gerçek bilgisayardan daha güçlüdür, ama çok daha yavaştır. Yapamadığı şey her soruyu yanıtlamaktır: Turing, hiçbir makinenin, her program ve girdi için, programın durup durmayacağına karar veremeyeceğini kanıtladı.

Sayaç neden hiç durmuyor?

Kuralları hiçbir zaman bir durma durumuna götürmez. Bandın sağ ucundaki ikili sayıya sürekli 1 ekler ve geri yürür, böylece sayı sonsuza dek büyür. Turing'in durma problemi, her makine için durup durmayacağını söyleyebilen genel bir yöntem olmadığını söyler; bu basit sayaç için bunu görebilirsiniz, ama yalnızca altı durumlu bazı makineler için henüz kimse bilmiyor.

Beş durumlu meşgul kunduz burada nasıl 47 milyon adım çalışabiliyor?

Bant her iki yönde büyüyen kompakt bir dizi olarak saklanır ve en hızlı ayarda uygulama ekran güncellemeleri arasında yüz binlerce adım çalıştırır; böylece tüm çalışma modern bir tarayıcıda birkaç saniye sürer. Diyagram yalnızca ilk 400 adımı kaydeder, çünkü 47 milyon satırlık bir resim hiçbir ekrana sığmaz.

Bir sunucuya bir şey gönderiliyor mu?

Hayır. Program tarayıcınızda çalışır; programınız ve girdiniz bu tarayıcının yerel depolama alanında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git