Java Programlama Zorunluluğu: Basit Turing Makinesi Yaratma - 1936'da canavarcı

1936'da matematikçi Alan Turing, Sahte bir şekilde basit bir hesaplama makinesi türü, Turing Makinesi . Turing asla bir Turing Makinesi kurmadı. Bunun yerine, hesaplanabilirlik çalışmasına yardımcı olmak için tasarladığı varsayımsal bir cihazdı - karmaşık problemlerin hesaplama adımlarıyla çözülebip çözülmeyeceği ve herhangi bir hesaplanabilir problemi çözebilecek bir makinenin tasarlanıp kurulamayacağı. (Turing makinelerinin geçmişi veya uygulaması hakkında daha fazla bilgi edinmek isterseniz İnternet'te onlarla ilgili birçok makale bulabilirsiniz. Sadece Turing makinesi aramak için herhangi bir arama sağlayıcısını kullanın.)

Bir Turing Makinesinin kullanımı basittir. Sadece birkaç temel kavramı bünyesinde barındırır:

1. Bir Turing Makinesi'nin kalbi, bilginin üzerine yazılacağı hücrelere bölünmüş sonsuz uzunlukta bir kasettir.

   Gerçek uygulamada, elbette hiçbir fiziksel cihaz sonsuz sayıda hücrelere sahip olamaz. Fakat bir Turing Makinesi teorisinde, bant sonsuzdur.

2. Her hücrenin üzerine yazılabilecek bilgiler, 0 veya 1 gibi tek bir simgeyle sınırlıdır. Ancak, bilgi ardışık hücrelerin birleştirilmiş değerleri tarafından gösterilebilir.

   Örneğin, sayısal değerleri ardarda 1 sembolü ile ve ardından 0 olarak gösterebilirsiniz. Böylece 1110 3 değerini temsil eder, çünkü üç tane 1 vardır; 111111011110, 6 ve 4 değerlerini temsil edebilir (altı 1 'in ardından bir sıfır, bunu takiben dört 1 ve ardından bir başka sıfır).

3. Turing Makinesi, bandın hücrelerinin her birinin üzerine (ve sadece bir tanesine) yerleştirilen okuma-yazma kafası içerir.

   Bu okuma-yazma kafası hücredeki sembolü okuyabilir. Ayrıca sembolü silebilir ve istenirse yerine yeni bir sembol yazabilir. Okuma-yazma kafasının konumlandırıldığı hücre, geçerli hücre veya kafa hücresi olarak anılır.

4. Kaset motorludur, böylece bir seferde tek bir hücre okuma-yazma kafası altında sağa veya sola hareket ettirilebilir.

5. Makine, alfabedeki bir harf gibi bir sembolle temsil edilen eyaletine sahiptir.

Herhangi bir bilgisayar gibi bir Turing Makinesi programlanabilir. Bununla birlikte, bir Turing Makinesi için bir program uzaktan bir Java programına benzemez.

Bunun yerine, Turing Machine programı, makinenin hangi eylemleri gerçekleştirmesi gerektiğini belirlemek için değerlendirilen basit kurallar grubudur. Her kural geçerli hücre belirli bir sembol içerdiğinde ve makine belirli bir durumda olduğunda alınacak bir eylemi tanımlar.Örneğin, bir kural mevcut hücre 1 içeriyorsa ve makine durumu "a" ise ne yapılacağını belirleyebilir.

Her kural üç eylemden herhangi birini belirleyebilir:

• Geçerli hücrenizi silin veya hücreye yeni bir değer yazın.

• Kaseti bir hücre sola veya bir hücre sağa taşıyın.

• Makinenin durumunu yeni bir duruma getirin.

Örneğin, bir kural, geçerli hücre 1 içeriyorsa ve makine durumu "a" ise, Turing Makinesi geçerli hücrede 0 yazar, kaseti bir hücre sağa ilerletmeli ve satırı değiştirmeliyiz makine durumu "b. "

Bir programa ek olarak, Turing Machine'in kaseti başlangıç ​​değerine sahip olabilir.

İşte bu; Bir Turing Makinesi'nin tüm tanımı budur. Basit olmasına rağmen, bir Turing Makinesi 2 + 2'den Mars'a bir roketin yörüngesine kadar her şeyi hesaplayabilir.

Bu zorluk için çok basit bir Turing Makinesi yaratmalısın. Sorunu basitleştirmek için Turing Makinesinin bu sürümünde aşağıdaki sınırlamaları kabul edin:

• Şerit sonsuz olmak zorunda değildir. Şeridi temsil etmek için herhangi bir Java özelliğini (dizi, dize veya koleksiyon) kullanabilirsiniz.

  (Şerit sonsuz olmak zorunda olmamasına rağmen, mevcut hücreden kolayca sola veya sağa hareket edebilmeniz gerekir.) Bir dizi kullanmayı seçerseniz, geçerli hücreye ait öğeyle başlamayın 0 çünkü buradan sola hareket edemezsiniz.)

• Bir hücre boş olabilir veya herhangi bir harf veya rakam içerebilir. Boş bir hücre alt çizgi karakteriyle gösterilir.

• Devlet tek bir alfasayısal karakter olabilir.

• Turing Machine programı bir metin dosyasından okunacaktır. Bu metin dosyası her satıra bir kural içeriyor. Her kural, boşluklarla ayrılmış ve her kural için ayrıntıları sağlayan beş karakter içerir:

  • Geçerli hücre: Geçerli hücre için eşleştirilecek değer.

  • Geçerli durum: Mevcut makine durumu için eşleştirilecek değer.

  • Yeni hücre: Yeni hücreye yazılacak değer. _ hücrenin silinmesi, * hücreyi değiştirmeden bırakın.

  • Hareket: Şeridi sola veya sağa hareket ettirmek için L veya R; H programı durdurmak; bandı taşımamak için başka herhangi bir karakter.

  • Yeni durum: Makine durumu için yeni değer.

• Örneğin, geçerli hücre 1 ve durum "a" olduğunda geçerli hücre 0'a ayarlanmalı, kaset bir hücre sola taşındı ve durum " b: "

  1 a 0 L b
  

  • Metin dosyasının ilk satırı, kasetin başlangıç ​​değerlerini gösteren bir dize içermelidir.

  • Metin dosyasının ikinci satırı ilk durumu içermelidir.

Aşağıdaki resim, örnek çözüm için kullanıcı arabirimini göstermektedir, ancak bu proje için istediğiniz herhangi bir kullanıcı arabirimi tasarımını kullanmakta serbestsiniz.

Olası bir Turing Machine arabirimi.

Arayüzü oluşturmak için bazı hususlar şunlardır:

• Değer ve geçerli hücre: En azından kasetin değerini göstermeli ve geçerli hücreyi vurgulamalısınız.

• Araçlar ve ekran: Ayrıca programın yürütülmesini başlatma, durdurma veya yeniden başlatma olanağını sağlamanız gerekir ve programın her adımının sonuçlarını görüntülemelisiniz.

• Program yürütme: Yüklenen programı başından sonuna kadar çalıştırmanın yanı sıra, kullanıcıya her adımda bir düğmeyi tıklayarak programa tek adım atmanın bir yolunu sağlayabilirsiniz programın.

• Program yükleniyor : Kullanıcıya bir Metin Dosyasından bir Turing Machine programı yüklemesine izin veren ve kullanıcının programı tekrar çalıştırması için makineyi sıfırlamasına izin veren düğmeler sağlamanız gerekir.

Sonsuz şerit uygulamak için bir ipucu: Şerit değerlerini tutmak için üç tane dize değişkeni kullanın; bir tanesi geçerli hücrede saklanan tek karakter, bir saniye geçerli hücrenin solunda ve üçüncüsü geçerli hücrenin sağındaki karakterleri. Ardından, birleştirme ve alt dizin işlemleri arasında doğru bir kombinasyon kullanarak, geçerli hücreyi kolayca sola veya sağa taşıyabilirsiniz.

Bu zorluğun çözümünü, Java All-in-One Dummies, 4. Edition ürün sayfasındaki İndirilenler sekmesinde bulabilirsiniz.

İyi şanslar!