Diyelim ki çok uzun zaman önce... Ama aslında Turing makinesinin yaratılmasından önce, çeşitli eylemleri gerçekleştirmek için makineler yaratıldı. Örneğin logaritmayı almanız gerekiyor, peki sayıyı okuyacak bir makineyi perçinleyelim ve logaritmayı alalım. Veya diyelim ki iki sayı eklemeniz gerekiyor - burada iki sayı eklemek için bir makineniz var. Evet ve şimdi bu tür makineler var, örneğin hesap makineleri. Ne yapabilirler? Toplama, çıkarma, çarpma ve mühendislik - hatta kosinüs veya sinüs alın. Bu aptal makinelerin, kendilerine kaydedilen eylemler dışında hiçbir şey yapamadığı ve yapamadığı ortaya çıktı.

Bu yüzden sayıları veya sembolleri değil, bir algoritmayı okuyacak ve onu çalıştıracak, yani programlanabilir bir makine yaratacak bir makine yaratmak çok ilginç olurdu. Turing'in yaptığı da budur (Turing'inkinin yanı sıra bu tür birçok soyutlama olduğunu söyleyeceğim). Ve böyle bir makinenin bir modelini buldu. Karmaşık algoritmaları yürütmek için tek ihtiyacınız olan bir şapka, sonsuz bir bant ve bantta yazılı değerleri değiştirme ve üzerinde hareket etme yeteneği olduğu ortaya çıktı. Bu soyutlamanın aslında gerçek bir makineye dönüştürülebileceği ortaya çıktı, makineye sonsuz bir bant sağlayamadığımız sınırlaması olan tek şey, ancak çok uzun bir bant yapabiliriz ;)

Geri çekilmek. Aslında Turing makinesinin nasıl çalıştığını anlatmaya gerek yok, dediğim gibi çok kolay bulunabiliyor. Bu nedenle, nasıl çalıştığını zaten bildiğinizi varsayacağız.

Turing makinesi bazı basit algoritmalar gerçekleştirir, bu tartışılmaz. Peki ya karmaşık olanlar? Ve örneğin, MT kullanarak bir döngü nasıl organize edilir? Veya dallanma nasıl anlaşılır? MT'nin döngüler ve dallar gerçekleştirebildiğini kanıtlayan teoremler olduğu ortaya çıktı, bu da bize çok basit bir mekanizma ile dallar ve döngüler gibi basit bloklardan programlar oluşturabileceğinizi söylüyor, bu da olabilecek her şeyi programlayabileceğiniz anlamına geliyor. programlanmış. Ve burada teorik olarak, hesaplanamayan fonksiyonların ve dolayısıyla çözülemeyen problemlerin olduğu ve bu problemlerin MT yardımıyla çözülemeyeceğine dair bir açıklama olmalıdır. İşte nasıl.

Ancak kimse bir Turing makinesinden daha havalı bir şey bulamadı, bu yüzden şu anda kullandığımız tüm programlama dilleri bir Turing makinesinden daha fazlasını programlayamaz. Turing bütünlüğü kavramının geldiği yer burasıdır; bu, bir dilin (veya başka bir şeyin) Turing makinesinde çalışan tüm algoritmaları yazabilmesi durumunda Turing'in tamamlanmış olduğu anlamına gelir. Ve üzerine bir Turing makinesi öykünücüsü yazarak dilin Turing'in eksiksiz olduğunu kanıtlayabilirsiniz. Bunlar pastalar.

Matematik açısından, gönderi saçmalık, ama ne için bir Turing makinesine ihtiyacımız olduğu açık. Aslında bu makine için algoritma yazmak ilginç bir bilmece. Turing makinesinde exp(x)'i programladıktan sonra algoritmanın ne olduğunu gerçekten anladığını söyleyenlerin olduğuna inanıyorum. Henüz denemedim, ama bu ilginç bir meydan okuma.

Bir Turing makinesi aşağıdaki nesnelerin bir koleksiyonudur.

• 1) harici alfabe A=(a 0 , a 1 , …, bir n );
• 2) dahili alfabe Q=(q 1 , q 2 ,…, q m ) - durum kümesi;
• 3) kontrol karakterleri seti (P, L, S)
• 4) hücrelere bölünmüş, her biri herhangi bir zamanda A alfabesinden yalnızca bir karakter içerebilen, her iki yönde de sonsuz bir bant;
• 5) birçok durumdan birinde olabilen bir kontrol cihazı

Boş bir hücrenin sembolü, harici alfabenin harfi olan 0'dır.

Durumlar arasında, makinenin çalışmaya başladığı ilk q 1 ve makinenin bir kez durduğu son (veya durma durumu) q 0 ayırt edilir.

Kontrol cihazı bant üzerinde sola ve sağa hareket edebilir, A harfinin harflerini okuyabilir ve bandın hücrelerine yazabilir.Kontrol cihazı aşağıdaki forma sahip komutlara göre çalışır.

q ben bir j > bir p X q k

Giriş şu anlama gelir: kontrol cihazı qi durumundaysa ve görüntülenen hücrede aj harfi yazıyorsa, (1) hücreye aj yerine ap yazılır, (2) makine görüntülemeye devam eder X=P ise az önce görüntülenenden sonraki sağ hücre veya X=L ise bir sonraki sol hücreyi görüntülemek veya X=C ise aynı bant hücresini görüntülemeye devam etmek, (3) kontrol cihazı q k durumuna girer.

Makinenin çalışması, koşula göre, belirli bir andaki q durumu ve o anda görüntülenen hücrenin a içeriği tarafından tamamen belirlendiğinden, her olası konfigürasyon q i a j için tam olarak bir kural vardır. Yalnızca makinenin durduğu son durum için hiçbir kural yoktur. Bu nedenle, dış alfabesi A=(a0, a1, …, an) ve iç alfabesi Q=(q1, q2,…, qm) olan Turing makine programı m (n+1)'den fazla komut içermez.

A alfabesindeki veya Q alfabesindeki veya A Q alfabesindeki bir kelime, karşılık gelen alfabedeki herhangi bir harf dizisidir. k-inci konfigürasyon altında, k-inci adımın başlangıcında üzerinde geliştirilen bilgilerle birlikte makinenin bandının görüntüsünü kastediyoruz (ya da A alfabesindeki kelime, k-inci adımın başında bantta yazılıdır). k-th adım), bu adımda hangi hücrenin görüntülendiğini gösterir ve araba hangi durumda? Yalnızca sonlu konfigürasyonlar anlamlıdır, yani. sonlu bir sayı hariç, bandın tüm hücrelerinin boş olduğu hücreler. Makinenin içinde bulunduğu durum nihai ise, bir konfigürasyonun nihai olduğu söylenir.

Turing makinesinin herhangi bir nihai olmayan konfigürasyonu ilk konfigürasyon olarak seçilirse, o zaman makinenin işi, nihai konfigürasyona ulaşılana kadar makine programına göre ilk konfigürasyonu sırayla (adım adım) dönüştürmektir. Bundan sonra Turing makinesinin işi tamamlanmış kabul edilir ve çalışmanın sonucu ulaşılan nihai konfigürasyondur.

A (а 0 ) = (a 1 , ..., an ) alfabesindeki boş olmayan bir b kelimesini, bandın ardışık hücrelerine yazılmışsa, makine tarafından standart bir konumda algılandığını söyleyeceğiz. diğer hücreler boştur ve makine, b kelimesinin yazıldığı hücrelerden en soldaki veya en sağdaki bir hücreyi tarar. Standart pozisyonda kelimeyi algılayan makine q 1 başlangıç ​​durumundaysa (sırasıyla q 0 durma durumunda) standart pozisyona ilk (son) denir.

B kelimesinin işlenmesi Turing makinesini son durumuna getiriyorsa, b için geçerli olduğu söylenir, aksi takdirde b için geçerli değildir (makine süresiz çalışır)

Bir örnek düşünün:

Harici alfabe A \u003d (0, 1) (burada 0 boş bir hücrenin sembolüdür), Q \u003d (q 0, q 1, q 2 ) ve aşağıdakilerle bir iç durum alfabesi olan bir Turing makinesi verildiğinde fonksiyonel diyagram (program):

q 1 0 > 1 Lq 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 Cq 1;

Bu program tablo kullanılarak yazılabilir.

İlk adımda komut şu şekilde çalışır: q 1 0 > 1 Л q 2 (kontrol cihazı q1 durumundadır ve izlenen hücreye 0 harfi, 0 yerine hücreye 1 yazılır, baş sola kaydırıldığında, kontrol cihazı q2 durumuna geçer), Sonuç olarak, makinede aşağıdaki konfigürasyon oluşturulur:

Son olarak, q 2 0 > 0 P q 0 komutu yürütüldükten sonra bir konfigürasyon oluşturulur.

Bu konfigürasyon nihaidir çünkü makine q 0 durmuş durumundadır.

Böylece, orijinal 110 kelimesi makine tarafından 101 kelimesine işlenir.

Ortaya çıkan konfigürasyon dizisi daha kısa bir şekilde yazılabilir (izlenen hücrenin içeriği, makinenin o anda bulunduğu durumun sağına yazılır):

11q 1 0 => 1q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Turing makinesi, A Q alfabesindeki kelimeleri dönüştürmek için bir kuraldan (algoritmadan) başka bir şey değildir, yani. konfigürasyonlar. Bu nedenle, bir Turing makinesini tanımlamak için, dış ve iç alfabelerini, programı belirtmeli ve simgelerden hangisinin boş bir hücreyi ve son durumu gösterdiğini belirtmelidir.

Turing Makinesi, 20. yüzyılın en ilgi çekici ve heyecan verici entelektüel keşiflerinden biridir. Herhangi bir bilgisayar görevini yerine getirmek için yeterince genel olan basit ve kullanışlı soyut bir bilgi işlem (bilgisayar ve dijital) modelidir. Basit açıklaması ve matematiksel analizi sayesinde teorik bilgisayar biliminin temelini oluşturur. Bu araştırma, genel kullanıcı bilgisayarlarında çözülemeyen bazı hesaplama problemlerinin olduğunun farkına varılması da dahil olmak üzere, dijital bilgisayarlar ve kalkülüs hakkında daha derin bir anlayışa yol açmıştır.

Alan Turing, bir bilgisayarla aynı temel yeteneklere sahip olacak en ilkel mekanik cihaz modelini tanımlamaya çalıştı. Turing, makineyi ilk olarak 1936'da Proceedings of the London Mathematical Society'de yer alan "Karar Verilebilirlik Problemine Bir Uygulama ile Hesaplanabilir Sayılar Üzerine" kitabında tanımladı.

Turing makinesi, içinden bir kağıt bant geçen bir okuma/yazma kafasından (veya "tarayıcı") oluşan bir bilgi işlem cihazıdır. Bant, her biri tek bir sembol taşıyan karelere bölünmüştür - "0" veya "1". Mekanizmanın amacı, hem giriş ve çıkış aracı olarak hem de hesaplamaların ara aşamalarının sonuçlarını depolamak için çalışan bir bellek görevi görmesidir. Cihaz nelerden oluşur Bu tür her makine iki bileşenden oluşur: Sınırsız bant. Her iki yönde de sonsuzdur ve hücrelere bölünmüştür. Makine kontrollü bir programdır, veri okumak ve yazmak için bir tarayıcı kafasıdır. Herhangi bir anda birçok eyaletten birinde olabilir.

Her makine iki sonlu veri serisini birbirine bağlar: A = (a0, a1, ..., am) giriş sembollerinin alfabesi ve Q = (q0, q1, ..., qp) durumlarının alfabesi. q0 durumuna pasif denir. Cihaza çarptığında işini bitirdiğine inanılıyor. Durum q1'e başlangıç ​​durumu denir - makine, başlangıçta olmak üzere hesaplamalarına başlar. Giriş kelimesi kasete her pozisyonda bir satırda bir harf yerleştirilir. Her iki tarafında sadece boş hücreler var.

Mekanizma nasıl çalışır?

Turing makinesinin bilgi işlem cihazlarından temel bir farkı vardır - depolama cihazının sonsuz bir bandı vardır, dijital cihazlar için ise böyle bir cihazın belirli bir uzunlukta bir şeridi vardır. Her görev sınıfı, yalnızca bir yapılandırılmış Turing makinesi tarafından çözülür. Farklı türden görevler, yeni bir algoritma yazmayı içerir. Bir durumda olan kontrol cihazı, bant boyunca herhangi bir yönde hareket edebilir. Hücrelere yazar ve onlardan son alfabenin karakterlerini okur. Hareket sırasında, girdi verilerini içermeyen konumları dolduran boş bir eleman tahsis edilir. Turing makinesinin algoritması, kontrol cihazı için geçiş kurallarını tanımlar. Yazma-okuma kafası için şu parametreleri ayarlarlar: hücreye yeni bir karakter yaz, yeni bir duruma geçiş, bant boyunca sola veya sağa hareket et.

Hareket Özellikleri

Turing makinesi, diğer bilgi işlem sistemleri gibi, kendine özgü özelliklere sahiptir ve bunlar algoritmaların özelliklerine benzer: Ayrıklık. Dijital makine, ancak bir önceki tamamlandıktan sonra bir sonraki adım olan n+1'e geçer. Tamamlanan her adım, n+1'in ne olacağını belirler. netlik Cihaz aynı hücre için yalnızca bir işlem gerçekleştirir. Alfabeden bir karakter girer ve bir hareket yapar: sola veya sağa. kararlılık. Mekanizmadaki her konum, verilen şemanın tek varyantına tekabül eder ve her aşamada eylemleri ve yürütme sırası belirsizdir. Yeterlik. Her adım için kesin sonuç Turing makinesi tarafından belirlenir. Program algoritmayı yürütür ve sonlu sayıda adımda q0 durumuna geçer. Kitle karakteri. Her cihaz, alfabede bulunan izin verilen kelimeler üzerinden tanımlanır. Turing Makina Fonksiyonları Algoritmaları çözerken, genellikle bir fonksiyonun uygulanması gerekir. Hesaplama için bir zincir yazma olasılığına bağlı olarak, fonksiyon algoritmik olarak karar verilebilir veya karar verilemez olarak adlandırılır. Doğal veya rasyonel sayılar kümesi olarak, bir makine için sonlu bir N alfabesindeki kelimeler, bir B kümesi dizisi olarak kabul edilir - ikili kod alfabesi B=(0.1) çerçevesindeki kelimeler. Ayrıca, hesaplamanın sonucu, algoritma "donduğunda" oluşan "tanımsız" değeri dikkate alır. İşlevi uygulamak için, sonlu alfabede resmi bir dilin olması ve doğru tanımları tanıma sorununun çözülebilir olması önemlidir.

Cihaz yazılımı

Turing mekanizması için programlar, ilk satır ve sütunun harici alfabenin sembollerini ve otomatın olası dahili durumlarının değerlerini - dahili alfabeyi içeren tablolarda düzenlenmiştir. Tablo verileri, Turing makinesinin kabul ettiği komutlardır. Görevler şu şekilde çözülür: şu anda bulunduğu hücrede kafa tarafından okunan harf ve otomat kafasının iç durumu, hangi komutların yürütülmesi gerektiğini belirler. Spesifik olarak, böyle bir komut, harici alfabenin sembollerinin ve tabloda bulunan dahili alfabenin sembollerinin kesiştiği yerde bulunur.

Hesaplamalar için bileşenler

Belirli bir sorunu çözmek için bir Turing makinesi oluşturmak için, bunun için aşağıdaki parametreleri tanımlamanız gerekir. dış alfabe. Bu, A işaretiyle gösterilen ve bileşenlerine harf adı verilen sonlu bir semboller kümesidir. Bunlardan biri - a0 - boş olmalıdır. Örneğin, ikili sayılarla çalışan bir Turing cihazının alfabesi şöyle görünür: A = (0, 1, a0). Bir kasete kaydedilen sürekli bir harf-sembol zincirine kelime denir. Otomat, insan müdahalesi olmadan çalışan bir cihazdır. Bir Turing makinesinde, sorunları çözmek için birkaç farklı duruma sahiptir ve belirli koşullar altında bir konumdan diğerine hareket eder. Bu tür taşıma durumları kümesi dahili alfabedir. O sahip harf atama Q=(q1, q2...) şeklindedir. Bu konumlardan biri - q1 - ilk, yani programı başlatan konum olmalıdır. Bir diğer gerekli unsur ise son durum olan yani programı sonlandıran ve cihazı durma konumuna getiren q0 durumudur.

Atlama masası.

Bu bileşen, makinenin mevcut durumuna ve okunmakta olan karakterin değerine bağlı olarak, cihaz taşıyıcısının davranışı için bir algoritmadır.-

Otomat için algoritma

Turing cihazının çalışma sırasında taşınması, her adım sırasında aşağıdaki işlem sırasını gerçekleştiren bir program tarafından kontrol edilir: Boş bir pozisyon da dahil olmak üzere bir pozisyona harici bir alfabe karakteri yazmak, boş olan da dahil olmak üzere içinde bulunan elemanı değiştirmek. Bir adım hücreyi sola veya sağa hareket ettirin. İç durumunuzu değiştirin. Bu nedenle, her bir karakter veya konum çifti için programlar yazarken, üç parametreyi doğru bir şekilde tanımlamak gerekir: ai - seçilen alfabe A'dan bir öğe, satır kaydırma yönü ("←" sola, "→" sağ, "nokta" - hareket yok) ve qk - cihazın yeni durumu Örneğin, 1 "←" komutu q2 "karakteri 1 ile değiştir" değerine sahiptir, şaryo kafasını bir adım hücre sola hareket ettirin ve duruma atlayın q2".

Sıklıkla karmaşıklığı değişen problemleri çözeriz: günlük, matematiksel vb. Bazılarını çözmek kolaydır, bazılarını çok düşünmek gerekir ve bazıları için asla bir çözüm bulamıyoruz.

Genel durumda, sorunu çözme yöntemi (varsa), sınırlı sayıda temel eylem kullanılarak tanımlanabilir.

Örneğin, ikinci dereceden bir denklemi çözme:

1. Denklemi standart forma dönüştürün \(a x^2 + b x + c = 0\)
2. \(a=0\) ise, bu Doğrusal Denklem\(x=\frac(-c)(b)\) çözümüyle. Sorun çözüldü. Aksi takdirde, 3. adıma gidin.
3. Diskriminantı hesaplayın \(D=b^2-4 a c\)
4. Denklem Çözümlerini Hesapla \(x_(1,2) = \frac(-b\pm\sqrt(D))(2 a)\). Sorun çözüldü.

Aşağıdaki sezgisel bir algoritma kavramını tanıtabiliriz:

Algoritma, herhangi bir başlangıç ​​verisi için, sonlu sayıda eylemde problemi çözme sonucunu elde etmek için icracının prosedürünü tanımlayan bir talimat setidir.

Bu elbette katı bir tanım değildir, ancak algoritma kavramının özünü tanımlar.

Algoritmalar belirli bir temele dayalı olarak derlenir. icracı ve bu nedenle icracının anlayabileceği bir dilde olmalıdır.

Algoritmanın yürütücüsü bir kişi olabilir veya bir bilgisayar veya örneğin bir dokuma tezgahı gibi başka bir otomat olabilir.

Algoritmaların aşağıdaki özellikleri ayırt edilir:

Algoritmanın ayrıklığı, belirli bir ayrı, iyi tanımlanmış adımlar (eylemler) dizisi olmalıdır. Bu eylemlerin her biri zaman içinde sınırlı olmalıdır. Algoritmanın her adımında kararlılık, bir sonraki adım sistemin mevcut durumu tarafından benzersiz bir şekilde belirlenir. Sonuç olarak, aynı ilk verilerde, algoritma kaç kez çalıştırılırsa çalıştırılsın her zaman aynı sonuçları verir. Anlaşılabilirlik Algoritma, icracının anlayabileceği bir dilde formüle edilmelidir. Eğer Konuşuyoruz Bir bilgisayar hakkında, algoritma yalnızca bilgisayar tarafından bilinen ve eylemlerinin sonucu kesin olarak tanımlanmış olan komutları kullanmalıdır. Sonluluk Algoritma sonlu sayıda adımda tamamlanmalıdır. Algoritmanın kütle karakteri, farklı girdi verisi kümelerine uygulanabilir olmalıdır. Başka bir deyişle, algoritma çözüme uygun olmalıdır. sınıf görevler. İkinci dereceden denklem örneğine dönersek, algoritma çözmek için uygundur. tüm ikinci dereceden denklemler, sadece bir veya daha fazla değil. Algoritma belirli bir sonuçla bitmelidir. Diyelim ki bir problemi çözerek veya çözümlerin yokluğunu keşfederek. Algoritma bir sonuca yol açmıyorsa, buna neden ihtiyaç duyulduğu da net değildir.

Bir problemi çözmenin her yolu bir algoritma değildir. Diyelim ki algoritma seçenek yok. Örneğin, çoğu yemek tarifleri Algoritma değiller çünkü “tadına tuz ekleyin” gibi ifadeler kullanıyorlar. Sonuç olarak, determinizm gerekliliği ihlal edilmektedir.

Çözümü olan her problem için değil, bir çözüm algoritması da vardır. Örneğin, görüntü tanıma sorunu hala büyük ölçüde çözülmemiştir ve kesinlikle titiz bir algoritma yardımıyla çözülmemiştir. Ancak sinir ağlarının kullanımı oldukça iyi sonuçlar vermektedir.

Genellikle, bir algoritma için kümeler vardır. kabul edilebilir veri girişi. Akşam yemeğini pişirmek için bir denklem çözme algoritması uygulamaya çalışmak garip olurdu ya da tam tersi.

Ek olarak, icracının olası eylemleri de sınırlıdır, çünkü herhangi bir eyleme izin verilirse, aralarında “kabul edilemez” olması gerekirdi.

Algoritmanın katı tanımı

Yukarıda verilen algoritma tanımı katı değildir. Bu bazı zorluklar yaratır. Özellikle, böyle bir tanımla, belirli bir problem sınıfının bir algoritma tarafından çözülebilir olup olmadığını kesin olarak kanıtlamak imkansızdır.

bir sınıf olduğu ortaya çıktı. algoritmik olarak çözülemeyen problemler- çözmek için bir algoritma oluşturmanın imkansız olduğu problemler. Ancak algoritmik kararsızlığı kesin olarak kanıtlamak için, önce bir algoritmanın kesin bir tanımına sahip olmak gerekir.

XX yüzyılın 20-30'larında, çeşitli matematikçiler, özellikle Alan Turing, Emil Leon Post, Andrey Andreevich Markov, Andrey Nikolaevich Kolmogorov, Alonzo Church ve diğerleri gibi bir algoritmanın titiz bir tanımı sorunu üzerinde çalıştılar. Çalışmaları sonunda algoritma teorisinin, hesaplanabilirlik teorisinin ve kalkülüse çeşitli yaklaşımların ve bu arada genel olarak programlamanın ortaya çıkmasına ve gelişmesine yol açtı. Çalışmalarının sonuçlarından biri, algoritmanın farklı şekillerde tanıtılan, ancak birbirine eşdeğer olan birkaç katı tanımının ortaya çıkmasıydı.

Turing'in tanımı üzerinde ayrıntılı olarak duracağız ve Post, Church ve Markov'un eşdeğer tanımlarını gözden geçireceğiz.

Turing makinesi

Bir algoritmanın resmi bir tanımını yapmak için Turing, Turing bilgisayarı veya basitçe bir Turing makinesi adı verilen soyut bir bilgisayar icat etti ve tanımladı.

Alan Turing (1912-1954)

Bir İngiliz matematikçi, mantıkçı, kriptograf, belki de dünyanın ilk "hacker"ı, bilgisayar biliminin ve yapay zeka teorisinin kökeninde yer aldı. Dünya Savaşı'nda Müttefik kuvvetlerin zaferine önemli katkılarda bulundu.

Turing makinesine girdi olarak kullanılır sözler, bazıları ile derlenmiş alfabe, yani bir küme karakterler.

Bir Turing makinesinin çıktısı da kelimelerdir.

Algoritmanın uygulandığı kelimeye denir. giriş. Çalışmadan çıkan kelime hafta sonu.

Algoritmanın uygulandığı kelime kümesine denir. algoritmanın kapsamı.

Kesin olarak söylemek gerekirse, herhangi bir nesnenin bir alfabede oluşturulmuş kelimeler biçiminde temsil edilebileceğini kanıtlamak imkansızdır - bunun için nesnenin katı bir tanımına ihtiyacımız olacaktır. Bununla birlikte, nesneler üzerinde çalışan rastgele seçilen herhangi bir algoritmanın, algoritmanın özünü değiştirmeden kelimeler üzerinde çalışacak şekilde dönüştürülebileceği doğrulanabilir.

Turing makinesinin açıklaması

Turing makinesinin bileşimi, hücrelere bölünmüş, her iki yönde de sınırsız bir bant ve bir kontrol cihazı (aynı zamanda olarak da adlandırılır) içerir. okuma/yazma kafası, ya da sadece makine) birçok eyaletten birinde olabilir. Kontrol cihazının olası durumlarının sayısı sonludur ve tam olarak verilmiştir.

Kontrol cihazı bant boyunca sola ve sağa hareket edebilir, hücrelere bazı sonlu alfabenin karakterlerini okuyabilir ve yazabilir. \(a_0\) veya \(\Lambda\) ile gösterilen, girdi verilerinin yazıldığı hücreler (sonlu bir sayı) dışında bandın tüm hücrelerini dolduran özel bir boş karakter tahsis edilir.

Kontrol cihazı, bu Turing makinesi tarafından uygulanan algoritmayı temsil eden geçiş kurallarına göre çalışır. Her geçiş kuralı, mevcut duruma ve mevcut hücrede gözlenen sembole bağlı olarak makineye bu hücreye yeni bir sembol yazması, yeni duruma gitmesi ve bir hücreyi sola veya sağa kaydırması talimatını verir. Turing makinesinin bazı durumları terminal olarak işaretlenebilir ve bunlardan herhangi birine geçiş, işin sonu, algoritmanın durması anlamına gelir.

Turing makinesi soyut bir kavram olsa da, böyle bir makineyi (sonlu bir bantla da olsa) hayal etmek yeterince kolaydır ve bunun gibi gösteri makineleri bile vardır:

Bir Turing makinesinin algoritmasını bir tablo şeklinde temsil etmek uygundur: tablonun sütunları banttaki mevcut (gözlenen) karaktere karşılık gelir, satırlar otomatın mevcut durumuna ve hücreler kaydına karşılık gelir. otomatın yürütmesi gereken komut.

Komut sırayla aşağıdaki yapıya sahip olabilir:

\[ a_k \left\lbrace \begin(matris) L \\ N \\ R \end(matris)\sağ\rbrace q_m \]

Önce geçerli hücreye yazılması gereken alfabenin karakteri gelir \(a_k\) , ardından otomatın sola (L), sağa (R) veya hiçbir yere (yerinde kal, N) hareketi belirtilen. Sonunda, otomatın \(q_m\) girmesi gereken yeni bir durum belirtilir.

Tablo hücresi, mevcut \(a_i\) karakteri ve otomatın \(q_j\) mevcut durumu tarafından açıkça belirlenir.

İşin başında Turing makinesinin olduğu konusunda hemfikir olalım. başlangıç ​​hali, \(q_1\) ile gösterilir ve durma durumu\(q_0\) algoritma biter ve makine durur.

Örnek vermek

Giriş kelimesine ekleyecek bir Turing makinesi için bir algoritma yazacağız. ondalık sayı, 1.

Ardından, tanımlayıcı olarak algoritma aşağıdaki gibi formüle edilebilir:

1. Sağa hareket ederek, giriş kelimesinin başlangıcını bulun
2. Sağa hareket ederek, giriş kelimesinin sonunu bulun
3. Giriş kelimesinin geçerli bitine bir tane ekleyin. 0'dan 8'e kadar bir sayı varsa çıkın. Aksi takdirde, 0 yazın, sola gidin ve 3. adıma dönün.

Bu algoritmayı tablo şeklinde yazıyoruz. Alfabe, 0'dan 9'a kadar olan sayılardan ve "boş karakter" \(\Lambda\) 'dan oluşur. Ayrıca, algoritma açıklamasının adımlarına karşılık gelen durma durumunu sayan otomatın 4 durumuna da ihtiyacımız var.

Başlangıç ​​durumunun \(1\) giriş kelimesinin başlangıcını arama, \(2\) giriş kelimesinin sonunu arama, \(3\)'in 1'in eklenmesi olduğunu kabul ediyoruz.

\(_(q_j)\ters eğik çizgi^(a_i)\)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛP1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛL3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Bir örnekle bu algoritmanın nasıl çalıştığını görelim. İlk satır banda karşılık gelir, ikincisi makinenin konumunu ve mevcut durumunu gösterir.

	1	9	9
1

Durum 1'de, otomat boş bir hücrenin üzerindedir. “ΛP1” tablosundan ilgili komut, yani hücreyi boş bırakın, sağa hareket edin ve durum 1'de kalın:

	1	9	9
	1

Artık otomat “1” değerini gözlemler. Karşılık gelen komut “1H2”, yani hücrede “1” bırakın, hareket etmeyin ve “2” durumuna gidin:

	1	9	9
	2

“2” durumunda, makine “1” değerini gözlemler. Karşılık gelen komut “1P2”, yani “1” bırakın, sağa hareket edin ve “2” durumunda kalın:

Durum tekrar ediyor:

Şimdi, durum 3'te ve “9” sembolünü gözlemleyerek, otomat “0L3” komutunu yürütür:

	1	9	0
		3

Durum tekrar ediyor:

Durum “0” – durumu durdur. Algoritma tamamlandı.

Resmi açıklama

Matematiksel olarak, bir Turing makinesi aşağıdaki gibi tanımlanabilir:

Turing makinesi (MT)

bu bir form sistemidir \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), nerede

• \(A\) MT alfabesinin sonlu bir sembol setidir
• \(a_0 \in A\) – alfabenin boş bir karakteri
• \(Q\) – sonlu MT durumları kümesi
• \(q_1 \in Q\) – MT'nin ilk durumu
• \(q_0 \in Q\) – MT son durumu (durma durumu)
• \(T = \(L, P, H\)\) MT'nin vardiya kümesidir
• \(\tau\) – MT programı, yani eşlemeyi tanımlayan bir fonksiyon \(\tau: A\times Q\ters eğik çizgi \(q_0\) \rightarrow A\times T \times Q\)

Algoritma teorisindeki anahtar, Turing'in tezi.

Gevşek bir ifadeyle Turing'in tezi şöyle ifade edilir:

Turing'in Tezi Algoritmik olarak çözülebilen herhangi bir problem için, bu problemi çözen bir Turing makinesi vardır. aksi takdirde, herhangi bir algoritma için eşdeğer bir Turing makinesi vardır.

Turing'in tezi, oldukça basit bir matematiksel aparat kullanarak algoritmalar hakkında konuşmamıza izin veriyor. Ayrıca Turing makinesinin kendisi evrensel çalıştırma cihazı ve böyle hayali bir makine yaratma olasılığı, evrensel bilgi işlem teknolojisinin yaratılması hakkında konuşmak için bir fırsat haline geldi.

Alternatif Algoritma Tanımları

Turing makinesinin dışında, Turing tanımına eşdeğer birkaç bağımsız tanım vardır.

Özellikle, Post makinesi aracılığıyla, Church'ün lambda hesabı, normal Markov algoritması aracılığıyla tanım.

Bu yöntemleri ele alalım.

Posta Makinesi

Turing'den bir yıl sonra, Amerikalı matematikçi Emil Leon Post bağımsız olarak Turing'inkinin biraz basitleştirilmiş hali olan başka bir soyut evrensel bilgisayar önerdi.

Posta makinesi iki basamaklı bir alfabe ile çalışır ve otomatın dahili durumu ile değiştirilir program satırı.

Aksi takdirde, Post makinesi Turing makinesine benzer: Bir otomat var ve hücrelerle dolu sonsuz bir bant var.

Posta makinesi aşağıdaki komutları yürütebilir:

1. 1 yazın, programın i. satırına gidin
2. 0 yazın, programın i. satırına gidin
3. Sola kaydır, programın i. satırına git
4. Sağa kaydırın, programın i. satırına gidin
5. Koşullu dallanma: gözlenen hücre 0 ise, programın i-inci satırına gidin, aksi takdirde programın j-inci satırına gidin.
6. Durmak.

Posta makinesinde ayrıca birkaç yasak komut vardır:

1. Zaten 1 olduğunda hücre 1'e yazın.
2. Zaten 0 olduğunda 0 hücresine yazma.

Bu tür olaylar bir kazaya yol açar.

Posta makinesi için programlar yazmak için aşağıdaki gösterim kullanılabilir:

1. ∨ i - 1 yazın, programın i-inci satırına gidin
2. × i – 0 yazın, programın i. satırına gidin
3. ← i - sola kaydır, programın i-inci satırına git
4. → i - sağa kaydır, programın i. satırına git
5. ? i; J- koşullu atlama: gözlenen hücrede 0 varsa programın i. satırına, yoksa programın j. satırına gidin.
6. ! - Dur.

Program örneği:

1. → 2 2. ? 1; 3 3. × 4 4. ← 5 5. !

Bu program, otomatın ilk konumunun sağındaki ilk etiketi (1) silecek ve solundaki hücrede otomatı durduracaktır.

Genel olarak, Posta makinesi öncüdür zorunlu C, Fortran vb. programlama dilleri.

Post makinesi Turing makinesine eşdeğerdir. Başka bir deyişle, herhangi bir Turing makine programı için eşdeğer bir Post makine programı yazabilirsiniz ve bunun tersi de geçerlidir.

Bu denkliğin önemli bir sonucu, herhangi bir alfabe ikili koda indirgenebilir.

Turing'in tezine benzer şekilde Post'un tezi de var.

Post'un tezi Her algoritma bir Post makinesi olarak temsil edilebilir.

Normal Markov Algoritması

Normal Markov algoritmaları, çeşitli alfabelerdeki kelimelere uygulanacak şekilde tasarlanmıştır.

Herhangi bir normal algoritmanın tanımı iki kısımdan oluşur:

1. alfabe algoritma
2. şemalar algoritma

Algoritmanın kendisi uygulanır sözler, yani, karakter dizileri alfabe.

Normal bir algoritmanın şeması, sonlu sıralı bir dizi sözde ikame formülleri, her biri olabilir basit veya son. Basit ikame formülleri \(L\to D\) biçimindeki ifadelerdir, burada \(L\) ve \(D\) algoritmanın alfabesinden (sırasıyla sol ve sağ kısımlar olarak adlandırılır) oluşan iki keyfi kelimedir. ikame formülü). Benzer şekilde, son ikame formülleri \(L\to\cdot D\) biçimindeki ifadelerdir, burada \(L\) ve \(D\) algoritmanın alfabesinden oluşan iki rastgele kelimedir.

\(\to\) ve \(\to\cdot\) yardımcı karakterlerinin algoritmanın alfabesine ait olmadığı varsayılır.

Normal algoritmayı rastgele bir \(V\) kelimesine uygulama süreci aşağıdaki eylem dizisidir:

1. \(V"\) algoritmanın önceki adımında elde edilen kelime (ya da mevcut adım ilkse orijinal kelime) olsun.
2. Yerine koyma formülleri arasında, sol kısmı \(V"\) içine dahil edilecek hiç kimse yoksa, algoritmanın işlemi tamamlanmış kabul edilir ve \(V"\) kelimesinin sonucu olarak kabul edilir. bu iş.
3. Aksi takdirde, sol kısmı \(V"\) içinde yer alan ikame formüllerinden ilki seçilir.
4. \(V"\) kelimesinin \(RLS\) biçimindeki tüm olası temsillerinden (burada \(R\) önek ve \(L\) sonektir), biri \(R) olacak şekilde seçilir. \) en kısadır, bundan sonra \(V"=RDS\) ikamesi gerçekleştirilir.
5. İkame formülü sonluysa, algoritma \(V"\) sonucuyla sona erdi. Aksi takdirde, 1. adıma gidin (sonraki adım).

Herhangi bir normal algoritma, bazı Turing makinelerine eşdeğerdir ve bunun tersi, herhangi bir Turing makinesi, bazı normal algoritmalara eşdeğerdir.

Normal algoritmalar için Turing'in tezinin bir benzerine genellikle denir. normalleştirme ilkesi.

Örnek vermek

Bu algoritma, ikili sayıları "tek" sayılara dönüştürür (negatif olmayan bir N tamsayısının kaydı bir N çubuk dizisidir). Örneğin, 101 ikili sayısı 5 çubuğa dönüştürülür: |||||.

Alfabe: ( 0, 1, | ) Kurallar:

1. 1 → 0|
2. |0 → 0||
3. 0 → (boş dize)

Kaynak satırı: 101 Yürütme:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

özyinelemeli fonksiyonlar

Bir Turing makinesine eşdeğer bir sistem, matematiksel fonksiyonlar temelinde oluşturulabilir. Bunu yapmak için aşağıdaki fonksiyon sınıflarını tanıtmamız gerekiyor:

• ilkel özyinelemeli işlevler
• genel özyinelemeli fonksiyonlar
• kısmen özyinelemeli fonksiyonlar

Son sınıf, Turing-hesaplanabilir fonksiyonların sınıfıyla aynı olacaktır (yani, bir Turing makinesi için bir algoritma tarafından değerlendirilebilen fonksiyonlar).

Özyinelemeli fonksiyonlar açısından bir algoritmanın tanımı, esasen lambda hesabının temelini oluşturur ve yaklaşım buna dayanır. fonksiyonel programlama.

İlkel Özyinelemeli İşlevler

İlkel özyinelemeli işlevler sınıfı şunları içerir: temel fonksiyonlar ve operatörler aracılığıyla taban olanlardan elde edilen tüm fonksiyonlar ikameler Ve ilkel özyineleme.

Temel özellikler şunları içerir:

• \(O()=0\) null işlevi, her zaman \(0\) döndüren bağımsız değişkeni olmayan bir işlevdir.
• Ardışıklık fonksiyonu \(S(x)=x+1\) herhangi bir doğal sayıya \(x\) atayan bir fonksiyondur. sonraki numara\(x+1\)
• Fonksiyonlar \(I_n^m(x_1,\ldots,x_n) = x_m\), nerede \(0

Sınıf işlevlerinin geri kalanını oluşturmak için aşağıdaki operatörler kullanılır:

• Değişiklikler. \(m\) değişkenlerinden oluşan bir \(f\) fonksiyonu ve her biri \(n\) değişkeninden \(g_1,\ldots,g_m\) \(g_1,\ldots,g_m\) için, \(g_k\) yerine koymanın sonucu içine \( f\) bir fonksiyondur \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)\(n\) değişkenlerinden.
• ilkel özyineleme. \(f(x_1,\ldots,x_n)\) \(n\) değişkenlerinin bir fonksiyonu olsun ve \(g(x_1,\ldots,x_(n+2))\) \('nin bir fonksiyonu olsun n+ 2\) değişkenler. Daha sonra, ilkel özyineleme operatörünü \(f\) ve \(g\) işlevlerine uygulamanın sonucu, formun \(n+1\) değişkeninin \(h\) işlevidir: \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

Kısmen özyinelemeli işlevler

Kısmen özyinelemeli işlevler sınıfı, ilkel özyinelemeli işlevleri ve ek olarak, bağımsız değişken minimizasyon operatörü kullanılarak ilkel özyinelemeli işlevlerden elde edilen tüm işlevleri içerir:

Argüman minimizasyon operatörü

\(f\), \(n\) değişkenlerinin \(x_i \in \mathbb(N)\) bir fonksiyonu olsun. Ardından, argüman minimizasyon operatörünün \(f\) işlevine uygulanmasının sonucu, \(n-1\) argümanının \(h\) işlevidir, şu şekilde tanımlanır:

\[ h(x_1,\ldots,x_(n-1)) = \min y, \] nerede \ Yani, \(h\), \(f\) değerinin sıfır olduğu \(f\) fonksiyonunun son argümanının minimum değerini döndürür.

İlkel özyinelemeli işlevler her zaman hesaplanabilirken, bazı bağımsız değişken değerleri için kısmen özyinelemeli işlevler tanımsız olabilir.

Daha kesin olarak, kısmen özyinelemeli işlevler, argümanların olası değerlerinin yalnızca bir kısmında tanımlandıkları için "kısmen tanımlanmış özyinelemeli işlevler" olarak adlandırılmalıdır.

Genel özyinelemeli fonksiyonlar

Genel özyinelemeli işlevler, herhangi bir bağımsız değişken değeri için tanımlanan tüm kısmen özyinelemeli işlevlerin bir alt sınıfıdır. Belirli bir kısmen özyinelemeli işlevin genel özyinelemeli olup olmadığını belirleme sorunu, algoritmik olarak karar verilemez. Bu bizi hesaplanabilirlik teorisi konusuna ve durma problemine getiriyor.

Hesaplanabilirlik teorisi ve durma problemi

Bir bütün olarak hayal gücümüz, çözülemeyen problemlerin, yani bir algoritma oluşturmanın imkansız olduğu problemlerin varlığını kabul eder.

Hesaplanabilirlik teorisi, bu tür problemlerin incelenmesiyle ilgilenir.

Algoritmik olarak çözülemeyen problemlere örnekler: sorunu durdur Ve türetilebilirlik tanıma sorunu. Onları daha ayrıntılı olarak ele alalım.

Durdurma problemi A algoritmasının ve \(x\) girişinin tanımı verildiğinde, \(A\) algoritmasının \(x\) girişinde durup durmadığını bulmak gerekir.

Durdurma sorunu algoritmik olarak karar verilemez. Hadi kanıtlayalım.

\(\Delta\)

Durma problemini çözen evrensel bir algoritma olsun. O halde algoritmaları açıklayan metinleri işleyen bir algoritma sınıfını ele alalım.

Durma probleminin çözümü için evrensel bir algoritmanın varlığından dolayı, bahsedilen sınıfa ait algoritmanın kendi metni üzerinde durup durmayacağını belirleyen bir algoritma bulunmaktadır. Böyle bir algoritmayı \(B\) belirtin.

Girdisi \(A\) algoritmasının metni olan ve kendi metnini işleyen bir \(C\) algoritması oluşturalım:

1. \(A\) üzerinde \(B\) algoritmasını çalıştırın.
2. \(B\) algoritması, \(A\) öğesinin metninde duracağını belirlerse, 1. adıma gidin. Aksi takdirde, 3. adıma gidin.
3. \(C\) algoritmasının sonu.

\(C\) algoritmasını \(C\) algoritmasına uygulamaya çalışırken, bariz bir çelişkiye ulaşırız: eğer \(C\) kendi metninde durursa, o zaman duramaz ve bunun tersi de geçerlidir. Bu nedenle, \(B\) algoritması yoktur. \(\değil \Delta\)

Durdurma probleminin daha genel bir formülasyonu, türetilebilirliği belirleme problemidir.

Türevlenebilirlik Tanıma Problemi

Belli bir alfabe, bu alfabenin kelimeleri (formülleri) ve bu alfabenin kelimeleri üzerinde bir biçimsel dönüşüm sistemi tanımlansın (yani, bir mantıksal hesap oluşturulur)

Herhangi iki \(R\) ve \(S\) kelimesi için, verilen mantıksal hesap içinde \(R\)'den \(S\)'ye giden bir tümdengelim zinciri var mı?

1936'da Alonzo Church, Church'ün teoremini kanıtladı.

Church teoremi Çıkarılabilirliği tanıma sorunu algoritmik olarak karar verilemez.

Kilise bunu kanıtlamak için lambda hesabının formalizmini kullandı. 1937'de Turing, kendisinden bağımsız olarak, Turing makinesi formalizmini kullanarak aynı teoremi kanıtladı.

Algoritmaların tüm tanımları birbirine eşdeğer olduğu için, belirli bir algoritma tanımıyla ilgili olmayan ve kavramla çalışan bir kavramlar sistemi vardır. hesaplanabilir fonksiyon.

Hesaplanabilir bir fonksiyon, bir algoritma tarafından değerlendirilebilen bir fonksiyondur.

Girdi ve çıktı verileri arasındaki ilişkinin bir algoritma kullanılarak tanımlanamadığı sorunlar vardır. Bu tür özellikler hesaplanamaz.

Hesaplanamayan bir fonksiyon örneği

\(\forall n \in \mathbb(N)\) için tanımlanan \(h(n)\) işlevini aşağıdaki gibi alın:

\[ h(n) = \begin(durumlar) 1, & \text(if )\pi\text( tam olarak )n\text( 9th) \\ 0, & \text(aksi takdirde ) \end( dizisini içerir vakalar) \]

Bu fonksiyon için \(1\) değerini alabiliriz, ancak, \(0\) değerini elde etmek için, \(\pi\) sayısının sonsuz ondalık açılımını kontrol etmemiz gerekir, ki bu açıkça sonluda imkansız. zaman. Bu fonksiyon dolayısıyla hesaplanamaz.

1920'ler sonrası ifadesi Hesap makinesiçalışan herhangi bir makineyi ifade eder insan bilgisayarıözellikle Church-Turing tezinin verimli yöntemlerine göre geliştirilmiş olanlar. Bu tez şu şekilde formüle edilmiştir: "Herhangi bir algoritma, karşılık gelen bir Turing makinesi veya kısmen özyinelemeli bir tanım biçiminde verilebilir ve hesaplanabilir işlevler sınıfı, kısmen özyinelemeli işlevler sınıfıyla ve Turing makinelerinde hesaplanabilen işlevler sınıfıyla örtüşür. ". Başka bir şekilde, Church-Turing tezi, elektronik bilgisayarlar gibi mekanik bilgi işlem cihazlarının doğası hakkında bir hipotez olarak tanımlanır. Yeterli zaman ve depolama alanına sahip olması koşuluyla, mümkün olan her türlü hesaplama bir bilgisayarda yapılabilir.

Sonsuzluk hesaplamaları üzerinde çalışan mekanizmalar analog tip olarak bilinir hale geldi. Bu tür mekanizmalardaki değerler, örneğin bir milin dönüş açısı veya elektrik potansiyelindeki fark gibi sürekli sayısal değerlerle temsil edildi.

Analog makinelerin aksine, dijital makineler sayısal bir değerin durumunu temsil etme ve her basamağı ayrı ayrı saklama yeteneğine sahipti. Dijital makineler, rastgele erişimli bellek aygıtının icadından önce çeşitli işlemciler veya röleler kullanıyordu.

İsim Hesap makinesi 1940'lardan beri kavramın yerini almaya başladı bir bilgisayar. O bilgisayarlar eskiden memurların yaptığı hesaplamaları yapabiliyordu. Değerler artık fiziksel özelliklere bağlı olmadığından (analog makinelerde olduğu gibi), sayısal donanıma dayalı mantıksal bir bilgisayar, tanımlanabilecek her şeyi yapabilmiştir. tamamen mekanik sistem .

Turing makineleri, hesaplama yeteneği üzerinde verilen sınırlarla neyin hesaplanabileceğini matematiksel olarak resmi olarak tanımlamak için tasarlandı. Bir Turing makinesi bir görevi gerçekleştirebiliyorsa, görevin Turing hesaplanabilir olduğu söylenir. Turing, esas olarak neyin hesaplanabileceğini belirleyebilecek bir makine tasarlamaya odaklandı. Turing, bir sayının yaklaşık değerini hesaplayabilen bir Turing makinesi olduğu sürece, bu değerin sayılabilir olduğu sonucuna vardı. Ek olarak, bir Turing makinesi AND, OR, XOR, NOT ve "If-Then-Else" gibi mantıksal operatörleri yorumlayarak