Post – Turing makinesi - Post–Turing machine

Bu makalenin birden çok sorunu var. Lütfen yardım et onu geliştir veya bu konuları konuşma sayfası. (Bu şablon mesajların nasıl ve ne zaman kaldırılacağını öğrenin) Bu makale gibi yazılır bir kılavuz veya rehber kitap. Lütfen yardım et bu makaleyi yeniden yaz bir tanımlayıcıdan tarafsız bakış açısıve tavsiye veya talimatı kaldırın. (Ağustos 2020) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) Bu makale gibi yazılmıştır araştırma makalesi veya bilimsel dergi bu kullanabilir aşırı teknik terimler veya yazılmayabilir ansiklopedik bir makale gibi. Lütfen geliştirmeye yardım et yeniden yazarak ansiklopedik tarz. (Ağustos 2020) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) Bu makalenin olması gerekebilir yeniden yazılmış Wikipedia'ya uymak için kalite standartları. Yardım edebilirsin. konuşma sayfası öneriler içerebilir. (Ağustos 2020) Bu makale için ek alıntılara ihtiyaç var doğrulama. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. Kaynakları bulun: "Post-Turing makinesi"  – Haberler  · gazeteler  · kitabın  · akademisyen  · JSTOR (Ağustos 2020) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Makale Turing makinesi Turing makinelerine genel bir giriş yaparken bu makale belirli bir Turing makineleri sınıfını kapsamaktadır.

Bir Post – Turing makinesi^[1] bir tür "program formülasyonu" Turing makinesi, bir varyantını içeren Emil Post 's Turing eşdeğeri model nın-nin hesaplama. Post'un modeli ve Turing'in modeli, birbirine çok benzese de bağımsız olarak geliştirildi. Turing'in makalesi Mayıs 1936'da yayınlanmak üzere alındı ​​ve ardından Ekim'de Postlar geldi.) Bir Post – Turing makinesi bir ikili alfabe, bir sonsuz sıra ikili depolama konumlar ve ilkel Programlama dili depolama yerleri arasında çift yönlü hareket ve içeriklerinin birer birer değiştirilmesi için talimatlar. "Post-Turing programı" ve "Post-Turing machine" isimleri tarafından kullanılmıştır. Martin Davis 1973–1974 (Davis 1973, s. 69 vf). 1980'de Davis, "Turing – Post programı" adını kullandı (Davis, Steen s. 241'de).

1936: Post modeli

1936 tarihli "Finite Combinatory Processes — Formulation 1" adlı makalesinde, Emil Post varsaydığı bir modeli tanımladı "mantıksal olarak eşdeğer -e yinelemeli olma ".

Post'un bir hesaplama modeli, bir hesaplama sırasında bir insan "bilgisayarın" gerçekleştireceği eylemlerin bir başka "atomizasyonunda" Turing makinesi modelinden farklıdır.^[2]

Post'un modelinde bir "sembol boşluk "iki yönlü sonsuz boşluk veya kutular dizisinden" oluşan, her kutu iki olası koşuldan birinde olabilir, yani "işaretli" (tek bir dikey vuruşla) ve "işaretsiz" (boş). , sonlu olarak - kutuların çoğu işaretlenmiş, geri kalanı işaretlenmemiş. Bir "işçi", sabit bir sonlu "yönler kümesine" göre, kutular arasında hareket eder, her seferinde yalnızca bir kutu içinde olur ve çalışır.Talimatlar ), sırayla numaralandırılır (1,2,3, ..., n). "Başlangıç ​​noktası olarak seçilen" bir kutudan başlayarak, işçi talimat 1'den başlayarak her seferinde bir talimat dizisini takip edecektir.

Özellikle, ben ^inci İşçiye verilen "yön" (talimat) aşağıdaki biçimlerden biri olacaktır:

(A) O işlemini gerçekleştirin_ben [Ö_ben = (a), (b), (c) veya (d)] ve sonra j yönünü takip edin_ben,^{[açıklama gerekli ]}

(B) Ameliyat yapmak (e) ve cevabın evet veya hayır olduğuna göre, j yönünü takip edin_ben'veya j_ben' ' ,^{[açıklama gerekli ]}

(C) Dur.

(Yukarıdaki girintili metin ve italikler orijinaldeki gibidir.) Post, bu formülasyonun gelişimin "ilk aşamalarında" olduğunu ve son "kesin formunda" "daha fazla esneklik" için çeşitli olasılıklardan söz ettiğini belirtir.

(1) kutuların sonsuzluğunu sonlu bir genişletilebilir sembol alanıyla değiştirmek, "işlem ilerledikçe verilen sonlu sembol uzayının gerekli genişlemesine izin vermek için ilkel işlemleri genişletmek",

(2) ikiden fazla sembolden oluşan bir alfabe kullanarak, "bir kutuyu işaretlemenin birden fazla yolu olan",

(3) Sonlu sayıda "işaretçi olarak hizmet verecek, işçinin tanımlayıp kutudan kutuya taşıyabileceği fiziksel nesneler" tanıtılması.

1947: Post'un Turing 5-tuples'in 4-tuples'e resmi olarak indirgenmesi

Makalede kısaca belirtildiği gibi Turing makinesi, Post, 1947 tarihli makalesinde (Bir Sorun Sorunun Özyinelemeli Çözümlenemezliği) Turing 5-tuples'i 4-tuple'a atomize etti:

"Dörtlülerimiz Turing geliştirmesindeki beşizlerdir. Yani, standart talimatlarımızın bir baskı (üst baskı) sipariş ettiği veya hareket, sola veya sağa, Turing'in standart talimatı her zaman bir baskı siparişi verir ve hareket, sağa, sola veya yok "(dipnot 12, Kararsız, s. 300)

Turing gibi, silme işlemini bir "S0" sembolü basmak olarak tanımladı. Ve böylece onun modeli sadece üç tipin dördüzlerini kabul etti (krş. Kararsız, s. 294):

q_ben S_j L q_l,

q_ben S_j R q_l,

q_ben S_j S_k q_l

Bu sırada, Turing devlet-makine konvansiyonunu hâlâ sürdürüyordu - varsayılan bir kavram kavramını resmileştirmemişti. ardışık bir sembolün belirli bir testi yürütmeyi başka bir yerde "dallara ayırana" kadar adımların yürütülmesi.

1954, 1957: Wang modeli

Burada sunulan Wang modelinin daha da fazla indirgenmesi için - yalnızca dört talimata - bakınız Wang B makinesi.

Wang (1957, ancak 1954'te ACM'ye sunulmuştur) sık sık (çapraz başvuru Minsky (1967), s. 200) kümedeki numaralandırılmış talimatları kullanan ikili bant Turing makinelerinin "program formülasyonunun" kaynağı olarak gösterilmektedir.

0 yaz

1 yaz

Sola hareket et

sağa hareket et

0'ı tarıyorsanız talimata git ben

1'i tarıyorsanız talimata git j

Herhangi bir ikili bant Turing makinesi, yukarıdaki talimatlar kullanılarak kolayca eşdeğer bir "Wang programına" dönüştürülür.

1974: ilk Davis modeli

Martin Davis bir lisans Emil Post'un öğrencisi. İle birlikte Stephen Kleene Doktorasını altında Alonzo Kilisesi (Davis (2000) 1. ve 2. dipnotlar s. 188).

Aşağıdaki modeli 1973–1974'te NYU'daki Courant Enstitüsüne bir dizi konferansta sundu. Bu, Davis'in "Post-Turing dili" ile "Post – Turing makinesi" adını resmi olarak uyguladığı modeldir.^[2] Talimatların sırayla yürütüldüğü varsayılır (Davis 1974, s. 71):

1978: ikinci Davis modeli

Aşağıdaki model bir deneme olarak görünüyor Hesaplama nedir? Steen sayfalarında 241–267. Bazı nedenlerden dolayı Davis, modelini bir "Turing-Post makinesi" olarak yeniden adlandırdı (sayfa 256'da bir geri kayma ile).

Aşağıdaki modelde Davis, Post'un "işaret / eğik çizgi" ye "1" ve boş kareye "0" sayılarını atar. Davis'ten alıntı yapmak gerekirse: "Artık Turing – Post Programlama Dilini tanıtmaya hazırız. Bu dilde yedi tür talimat vardır:

"YAZDIR 1

"YAZDIR 0

"SAĞA GİT

"SOLA GİT

"IF ADIMINA GİT 1 TARANMIŞ

"IF ADIMINA GİT 0 TARANMIŞ

"DUR

"Bir Turing-Post programı, her biri bu yedi türden biri olan talimatların bir listesidir. Elbette gerçek bir programda harf ben ya beşinci ya da altıncı türden bir adımda, belirli (pozitif tam) bir sayı ile değiştirilmelidir. "(Davis, Steen, s. 247).

1994 (2. baskı): Davis – Sigal – Weyuker'in Turing Sonrası program modeli

"Sunduğumuz Turing'in formülasyonu, esasen Emil Post tarafından verilene daha yakın olsa da, Turing'in bu formülasyonu çok uygun kılan hesaplama analiziydi. Bu dil, teorik bilgisayar biliminde temel bir rol oynadı." (Davis ve diğerleri (1994) s. 129)

Bu model, birden çok simgenin yazdırılmasına izin verir. Model, S yerine B'ye (boş) izin verir₀. Bant her iki yönde de sonsuzdur. Ya kafa ya da bant hareket eder, ancak SAĞ ve SOL tanımları her iki durumda da her zaman aynı sonucu belirtir (Turing aynı kuralı kullandı).

YAZDIR σ; Taranan sembolü σ ile değiştirin

EĞER σ L GİTMEKSE; taranan sembol σ SONRA L etiketli "ilk" talimata gidin

SAĞ; Şu anda taranan karenin hemen sağındaki kareyi tara

SOL; Şu anda taranan karenin hemen solundaki kareyi tara

Bu model, burada gösterildiği gibi yukarıda sunulan ikili {0, 1} sürümlere indirgenir:

YAZDIR 0 = SİL; Taranan sembolü 0 ile değiştir = B = BOŞ

YAZDIR 1; Taranan sembolü 1 ile değiştirin

IF 0 GOTO L; EĞER taranan sembol 0 ise SONRA L etiketli "ilk" talimata gidin

IF 1 GOTO L; EĞER taranan sembol 1 ise SONRA L etiketli "ilk" talimata gidin

SAĞ; Şu anda taranan karenin hemen sağındaki kareyi tara

SOL; Şu anda taranan karenin hemen solundaki kareyi tara

Post-Turing makinesi örnekleri

Turing beşlilerini bir Turing Sonrası talimatlar dizisine atomize etme

Aşağıdaki "indirgeme" (ayrıştırma, atomize etme) yöntemi - 2-sembollü Turing 5-demetinden 2-sembollü Turing Sonrası talimat dizisine kadar - Minsky (1961) 'de bulunabilir. Bu indirgemenin "a program ... bir dizi Talimatlar"ruhu içinde Hao Wang'ın B-makine (italik orijinal, çapraz başvuru Minsky (1961) s. 439).

(Minsky'nin "alt rutin" olarak adlandırdığı şeye indirgenmesi, 7 Turing Sonrası talimat yerine 5 ile sonuçlanır. Wi0'ı atomize etmedi: "Si0 sembolünü yaz; yeni Mi0 durumuna git" ve Wi1: "Si1 sembolünü yaz; yeni Mi1 "durumuna gidin. Aşağıdaki yöntem Wi0 ve Wi1'i daha fazla atomize eder; diğer tüm açılardan yöntemler aynıdır.)

Turing 5-demetlerinin Turing Sonrası talimatlara indirgenmesi "verimli" bir Turing Sonrası programla sonuçlanmayabilir, ancak orijinal Turing programına sadık kalacaktır.

Aşağıdaki örnekte, 2 durumlu her Turing 5-tuple meşgul kunduz dönüşür

(i) bir başlangıç ​​koşullu "atlama" (goto, dallanma), ardından

(ii) "0" durumu için 2 şerit eylem talimatı - Yazdır veya Sil veya Yok, ardından Sol veya Sağ veya Hiçbiri, ardından

(iii) "0" durumu için bir sonraki talimata koşulsuz bir "atlama"

(iv) "1" durumu için 2 şerit eylem talimatı - Yazdır veya Sil veya Yok, ardından Sol veya Sağ veya Hiçbiri, ardından

(v) "1" durumu için bir sonraki talimata koşulsuz "atlama"

Toplamda 1 + 2 + 1 + 2 + 1 = 7 Turing durumu başına talimatlar.

Örneğin, 2-durumlu meşgul kunduzun "A" Turing-durumu, iki satırlık 5-tuple olarak yazılır:

Tablo sadece tek bir Turing "talimatını" temsil eder, ancak bir tanesi "başın altındaki bant sembolü = 1" durumu için, diğeri "başın altındaki bant sembolü = 0 olmak üzere iki 5-tuple satırından oluştuğunu görürüz. ". Turing gözlemlendi (Kararsız, s. 119) soldaki iki sütun - "m-konfigürasyonu" ve "sembol" - makinenin mevcut "konfigürasyonunu" temsil eder - o anda hem Şerit hem de Tabloyu içeren durumu - ve son üç sütun onun sonraki "davranışıdır". Makine aynı anda iki "durumda" olamayacağından, makinenin yapılandırmalardan birine veya diğerine "dallanması" gerekir:

"Konfigürasyon dalı" (J1 xxx) veya (J0 xxx) sonrasında, makine iki ardışık "davranıştan" birini izler. Bu iki davranışı tek bir satırda listeliyoruz ve sırayla (benzersiz olarak) numaralandırıyoruz (veya etiketliyoruz). Her atlamanın (dal, git) altına atlamasını "sayı" (adres, konum) yerleştiririz:

Turing Sonrası makine kurallarına göre Yazdır, Sil, Sol ve Sağ talimatlarının her biri iki eylemden oluşur:

(i) Bant eylemi: {P, E, L, R}, sonra

(ii) Tablo eylemi: sırayla bir sonraki talimata git

Ve Turing Sonrası makine kurallarına göre koşullu "sıçramalar" J0xxx, J1xxx iki eylemden oluşur:

(i) Bant eylemi: başın altındaki banttaki sembole bakın

(ii) Tablo eylemi: Sembol 0 (1) ve J0 (J1) ise, o zaman xxx'e git, yoksa sırayla sonraki talimata git

Ve Turing Sonrası makine kurallarına göre koşulsuz "atlama" Jxxx tek bir eylemden oluşur veya 2 eylem sırasını düzenlemek istiyorsak:

(i) Bant eylemi: başın altındaki banttaki sembole bakın

(ii) Tablo eylemi: Sembol 0 ise xxx'e gidin, aksi takdirde sembol 1 ise xxx'e gidin.

Hangi ve kaç tane atlama gereklidir? Koşulsuz atlama Jxxx basitçe J0 hemen ardından J1 (ya da tam tersi). Wang (1957) ayrıca sadece bir koşullu sıçramanın gerekli olduğunu, yani J0xxx veya J1xxx. Bununla birlikte, bu kısıtlama ile makinenin talimat yazması zorlaşır. Genellikle sadece iki tane kullanılır, yani.

(ben) { J0xxx, J1xxx}

(ii) { J1xxx, Jxxx}

(iii) { J0xxx, Jxxx},

ancak üçünün de kullanımı { J0xxx, J1xxx, Jxxx} fazladan talimatları ortadan kaldırır. Sadece kullandığımız 2 durumlu Meşgul Kunduz örneğinde { J1xxx, Jxxx}.

2 durumlu meşgul kunduz

Misyonu meşgul kunduz durdurmadan önce mümkün olduğunca çok sayıda yazdırmaktır. "Yazdır" komutu bir 1 yazar, "Sil" komutu (bu örnekte kullanılmamaktadır) bir 0 yazar (yani P0 ile aynıdır). Bant "Sol" veya "Sağ" hareket eder (yani "kafa" sabittir).

2 durumlu Turing makinesi için durum tablosu meşgul kunduz:

2 durumlu meşgul kunduzun Turing Sonrası versiyonu için talimatlar: tüm talimatların aynı satırda ve sırayla olmasına dikkat edin. Bu, "Turing" sürümünden önemli bir sapmadır ve "bilgisayar programı" olarak adlandırılanla aynı formattadır:

Alternatif olarak, tabloyu bir dizge olarak yazabiliriz. "Parametre ayırıcıları" ":" ve yönerge-ayırıcılarının "" kullanımı tamamen bizim seçimimizdir ve modelde görünmez. Durum diyagramı kurallarının talimatlarla nasıl birleştirileceğine ilişkin bazı yararlı fikirler için (ancak Booth (1967) s. 374'e ve Boolos ve Jeffrey (1974, 1999) s. 23'e bakın) - yani, atlayışların hedefi). Hemen aşağıdaki örnekte talimatlar ardışık "1" den başlayarak ve parametreler / "işlenenler" talimatlarının / "işlem kodlarının" parçası olarak kabul edilir:

J1: 5, P, R, J: 8, P, L, J: 8, J1: 12, P, L, J1: 1, P, N, J: 15, H

İki durumlu meşgul bir kunduzun durum diyagramı (küçük çizim, sağ köşe), "Turing" durumu başına 7 Turing Sonrası talimat ikamesi ile eşdeğer Turing Sonrası makineye dönüştürülür. HALT talimatı 15. durumu ekler:

2-durumlu meşgul kunduzun, Turing sonrası makinenin tüm ara adımlarının gösterildiği bir "çalışması":

Notlar

Referanslar

• Stephen C. Kleene, Meta-Matematiğe Giriş, North-Holland Publishing Company, New York, 10. baskı 1991, ilk kez 1952'de yayınlandı. Bölüm XIII, Turing makinelerinin mükemmel bir açıklamasıdır; Kleene, açıklamasında Post-benzeri bir model kullanıyor ve Turing modelinin daha fazla atomize edilebileceğini kabul ediyor, bakınız dipnot 1.
• Martin Davis, düzenleyici: Kararsız Önermeler, Çözümlenemeyen Sorunlar ve Hesaplanabilir Fonksiyonlar Üzerine Kararsız, Temel Makaleler, Raven Press, New York, 1965. Makaleler, Gödel, Kilise, Rosser, Kleene ve Post.
• Martin Davis, "Hesaplama nedir", Bugün Matematik, Lynn Arthur Steen, Vintage Books (Random House), 1980. Harika bir küçük kağıt, belki de Turing Machines hakkında yazılmış en iyi makale. Davis, Turing Machine'i Post'un hesaplama modeline göre çok daha basit bir modele indirgiyor. Emil Post'un küçük bir biyografisini içerir.
• Martin Davis, Hesaplanabilirlik: Barry Jacobs'un Notları ile, Courant Matematik Bilimleri Enstitüsü, New York Üniversitesi, 1974.
• Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) Hesaplanabilirlik, Karmaşıklık ve Diller: Teorik Bilgisayar Biliminin Temelleri - 2. baskı, Academic Press: Harcourt, Brace & Company, San Diego, 1994 ISBN  0-12-206382-1 (İlk baskı, 1983).
• Fred Hennie, Hesaplanabilirliğe Giriş, Addison – Wesley, 1977.
• Marvin Minsky, (1961), Post'un 'Etiket' probleminin Özyinelemeli Çözümlenemezliği ve Turing Makineleri Teorisindeki diğer Konular, Annals of Mathematics, Cilt. 74, No. 3, Kasım 1961.
• Roger Penrose, İmparatorun Yeni Zihni: Bilgisayarlar, Akıllar ve Fizik Kanunları ile ilgili, Oxford University Press, Oxford England, 1990 (düzeltmelerle). Cf. Bölüm 2, "Algoritmalar ve Turing Makineleri". Aşırı karmaşık bir sunum (daha iyi bir model için Davis'in makalesine bakın), ancak Turing makinelerinin kapsamlı bir sunumu ve durdurma sorunu ve Kilise'nin lambda hesabı.
• Hao Wang (1957): "Turing'in bilgi işlem makineleri teorisinin bir çeşidi", Bilgisayar Makineleri Derneği Dergisi (JACM) 4, 63–92.