Şimdiye kadar algoritmalar, programlar, tercümanlar, adımlama vb. hakkında konuşurken programlama deneyimine başvurmak bizim için uygun oldu. Bu, okuyucunun onları kolayca geri yükleyebileceği (veya en azından, her okuyucunun hayatında Pascal'da bir Pascal tercümanı yazmadığına inandığı) bahanesiyle belirli algoritmalar oluşturmanın ayrıntılarını görmezden gelmemize izin verdi.

Ancak bazı durumlarda bu yeterli değildir. Örneğin, tanımı programlar hakkında hiçbir şey söylemeyen bazı problemlerin algoritmik çözülemezliğini kanıtlamak istiyoruz (örneğin, bu bölümde, eşitlik problemi kelimesinin çözülemezliğini üreteçler ve ilişkiler tarafından verilen yarı gruplarda kanıtlayacağız) . Genelde böyle yapılır. Durma probleminin bu probleme indirgendiğini gösteriyoruz. Bunu yapmak için, keyfi bir algoritmanın işleyişini incelenmekte olan problem açısından modelliyoruz (bunun ne anlama geldiği aşağıdaki örnekte görülecektir). Aynı zamanda, algoritmanın tanımının olabildiğince basit olması bizim için önemlidir.

Yani planımız şu. Oldukça kolay tanımlanmış bir makine sınıfını tanımlayacağız (birçok şekilde seçilebilir, sözde Turing makinelerini kullanacağız), sonra herhangi bir hesaplanabilir işlevin böyle bir makinede değerlendirilebileceğini ilan edeceğiz ve sonra Turing makinesini durdurma sorununun, bir yarı gruptaki sözcüklerin eşitliği sorununa indirgenebileceğini gösterin.

Basit hesaplama modellerinin önemli olmasının bir başka nedeni (birçok farklı Turing makinesi, adres makinesi vb. vardır) hesaplama karmaşıklığı teorisiyle ilgilidir. kurşun zamanı programlar. Ancak bu soru, klasik algoritma teorisinin ötesine geçiyor.

Turing makineleri: tanım

Turing makinesi her iki yönde de sonsuzdur kaset, karelere bölünmüş ( hücreler). Her hücre, adı verilen sabit (belirli bir makine için) sonlu kümeden bazı karakterler içerebilir. alfabetik olarak bu makine. Alfabenin sembollerinden biri vurgulanır ve "boşluk" olarak adlandırılır, başlangıçta tüm bandın boş olduğu, yani boşluklarla dolu olduğu varsayılır.

Bir Turing makinesi, özel bir okuyucu ve yazıcı kullanarak bir bandın içeriğini değiştirebilir. kafalar, bant boyunca hareket eder. Baş her an hücrelerden birinin içindedir. Turing makinesi, gördüğü sembol hakkında kafadan bilgi alır ve buna (ve dahili durumuna) bağlı olarak ne yapacağına, yani mevcut hücreye hangi sembolü yazacağına ve bundan sonra nereye hareket edeceğine karar verir (sol, doğru ya da yerinde kal). Bu aynı zamanda makinenin iç durumunu da değiştirir (kaset dışında makinenin sınırlı bir belleğe, yani sınırlı sayıda dahili duruma sahip olduğunu varsayıyoruz). İşe nereden başlayacağımız ve ne zaman bitireceğimiz konusunda da anlaşmamız gerekiyor.

Bu nedenle, bir Turing makinesini tanımlamak için aşağıdaki nesneler belirtilmelidir:

Atlama tablosu şu şekilde düzenlenmiştir: her çift için bir üçlü gösterilir. Burada kaydırma -1 (sol), 0 (yerinde) ve 1 (sağ) sayılarından biridir. Dolayısıyla, geçiş tablosu, durumun nihai olmadığı çiftler üzerinde tanımlanan S x A -> S x A x (-1,0,1) tipinde bir fonksiyondur.

Turing makinesinin davranışını açıklamaya devam ediyor. her an biraz var konfigürasyon, bandın içeriğinden (resmen konuşursak, bandın içeriği keyfi bir eşlemedir Z -> A ), başın mevcut konumu (bazı tamsayılar) ve makinenin mevcut durumundan (S elemanı) oluşur. Konfigürasyonun bir sonrakine dönüşümü doğal kurallara göre gerçekleşir: belirli bir durum ve belirli bir sembol için yapılması gerekenleri tabloya bakarız, yani makinenin yeni durumunu buluruz, sembolünü belirtilene getirin ve ardından kafayı sola, sağa hareket ettirin veya yerinde bırakın. Bu durumda, yeni durum son durumlardan biri ise, makinenin çalışması sona erer. Geriye makinenin girdisine nasıl bilgi sunacağımız ve çalışmasının sonucu olarak neyin kabul edileceği konusunda anlaşmaya varmak kalıyor. Boşluğa ek olarak makinenin alfabesinin 0 ve 1 karakterlerini (ve ayrıca muhtemelen başka bazı karakterleri) içerdiğini varsayacağız. Makinenin girdisi ve çıktısı, sonlu sıfır ve bir dizileri (ikili sözcükler) olacaktır. Girilen kelime boş bir teybe yazılır, makine kafası ilk hücresine yerleştirilir, makine başlatılır ve başlatılır. Makine durursa sonuç, baş konumdan başlayarak sağa doğru hareket eden (0 ve 1 dışında bir karakter görünene kadar) okunabilen bir ikili sözcüktür.

Bu nedenle, herhangi bir Turing makinesi, ikili sözcükler üzerinde bazı kısmi işlevler tanımlar. Tüm bu tür işlevleri çağırmak doğaldır. Turing makinelerinde hesaplanabilir.

Turing makineleri: tartışma

Elbette, tanımımız değiştirilebilecek pek çok spesifik detay içermektedir. Örneğin, bir bant yalnızca bir yönde sonsuz olabilir. Makineye iki bant verebilirsiniz. Makinenin yeni bir karakter yazabileceğini veya hareket edebileceğini, ancak ikisini birden yapamayacağını varsayabiliriz. Diyelim ki tam olarak 10 karakter olması gerektiğini varsayarak alfabeyi sınırlamak mümkündür. Sonunda, çalışmanın sonucu dışında kasette hiçbir şey olmamasını talep edebilirsiniz (geri kalan hücreler boş olmalıdır). Bütün bunlar ve diğer pek çok değişiklik, Turing makinelerinde hesaplanabilen işlevlerin sınıfını değiştirmez. Elbette zararsız değişiklikler de yok değil. Örneğin, arabanın sola hareket etmesini yasaklarsanız, bu durumu özünde kökten değiştirecek, artık eski kayıtlara dönmek mümkün olmayacağından kaset işe yaramaz hale gelecektir.

Hangi değişikliklerin zararsız, hangilerinin zararsız olduğu nasıl anlaşılır? Görünüşe göre, burada Turing makinelerinde en azından küçük bir pratik programlama deneyimi gerekiyor. Bundan sonra, makinenin yeteneklerini programları tam olarak yazmadan, ancak yalnızca yaklaşık bir açıklamayla yönlendirilerek hayal etmek zaten mümkün. Örnek olarak, giriş kelimesini ikiye katlayan (giriş X kelimesi ise XX kelimesini üreten) bir makineyi açıklayalım.

Makine bir boşluk görürse (girilen sözcük boştur), makineden çıkar. Değilse, mevcut karakteri hatırlar ve bir işaret koyar (alfabede 0 ve 1 karakterlerine ek olarak, bunların "işaretli varyantları" ve ) da olacaktır. Sonra sağdaki boş bir hücreye gider ve ardından hatırlanan karakterin bir kopyasını oraya yazar. Sonra işarete kadar sola hareket eder; kendini işarete gömerek, geri adım atar ve bir sonraki karakteri hatırlar ve bu, kelimenin tamamını kopyalayana kadar devam eder.

Biraz deneyimle, tüm bu ifadelerin arkasında Turing makinesi için programın belirli parçalarını görebilirsiniz. Örneğin, "bir karakteri ezberle ve sağa git" sözcükleri, biri sıfırın depolandığı durum, diğeri birin depolandığı durum için ve her grup içinde sağa doğru hareket olmak üzere iki durum grubu olduğu anlamına gelir. ilk boş hücreye programlanır.

Biraz daha deneyimle, karakterlerin kopyalarının orijinal kelimenin karakterlerinden hiçbir farkı olmadığı için, bu açıklamanın kelimenin tamamı kopyalandığında bir durdurma mekanizması sağlamama hatası olduğunu anlayabilirsiniz. Hatanın nasıl düzeltileceği de açıktır, özel karakterleri ve kopyaları yazmak gerekir ve son aşamada tüm işaretleri kaldırın.

77 . Bir kelimeyi geriye doğru çeviren ters fonksiyonunun bir Turing makinesinde hesaplanabilir olduğunu gösterin.

Gayri resmi akıl yürütmeye başka bir örnek: neden 0 , 1 ve boş karakter dışında ek karakterler kullanamayacağınızı açıklayalım. N karakterlik büyük bir alfabeye sahip bir makine olsun. Eskisinin çalışmasını simüle edecek yeni bir makine yapalım, ancak eskisinin her hücresi yenisinin k hücrelik bir bloğuna karşılık gelecek. Bloğun boyutu (k sayısı), bloğun içinde büyük alfabenin tüm karakterlerini sıfırlar ve birlerle kodlamak mümkün olacak şekilde sabitlenecektir. İlk karakterler 0 , 1 ve boş, 0'ın ardından (k-1) boş karakter, 1'in ardından (k-1) boş karakter ve k boş karakter grubu olarak kodlanacaktır. İlk olarak, giriş kelimesinin harflerini k mesafesine taşımanız gerekir; bu, ek karakterler olmadan yapılabilir (son harfe ulaştıktan sonra onu uzaklaştırın, ardından bir sonrakine ulaşın, onu ve sonuncuyu taşıyın vb. ); kişinin bir kelimenin sonunu k'den fazla boş karakterin izlediği bir konum olarak tanımlayabileceğini anlaması yeterlidir. Açıktır ki, bu süreçte hafızada sınırlı miktarda bilgi saklamamız gerekir, yani bu mümkündür. Bundan sonra, orijinal makinenin çalışmasını adımlar halinde simüle etmek zaten mümkündür ve bunun için de sınırlı bir bellek (belirli sayıda durum) yeterlidir, çünkü simüle edilen makinenin kafasının yalnızca küçük bir komşuluğu vardır. bizim için önemli Son olarak, sonucu geri sıkıştırmamız gerekiyor.

Tartışmayı sonlandırmak için, yukarıda vaat edilen herhangi bir hesaplanabilir fonksiyonun bir Turing makinesinde hesaplanabilir olduğu argümanını sunuyoruz. Bir kişinin hesaplayabileceği bir fonksiyon olsun. Aynı zamanda, elbette bir kalem ve kağıt kullanmalıdır, çünkü Bilgi miktarı"aklında" tutabileceği şeyler sınırlıdır. Ayrı kağıtlara yazdığını varsayacağız. Geçerli sayfaya ek olarak, sağda bir yığın kağıt ve solda bir yığın kağıt vardır; mevcut sayfayı bunlardan herhangi birine koyabilir, onunla işi tamamlayabilir ve bir sonrakini başka bir yığından alabilirsiniz. Adamın bir kalemi ve silgisi var. Çok küçük harfler görünmediğinden, sayfanın açıkça ayırt edilebilen durumlarının sayısı sonludur ve her an sonlu (çok büyük de olsa) bir alfabeden bir harfin kağıda yazıldığını varsayabiliriz. İnsanın da sınırlı bir hafızası vardır, öyle ki durumu sonlu bir kümenin bir öğesidir. Aynı zamanda, verilen durumda başlayan, verilen içeriğe sahip sayfa üzerindeki çalışmasının nasıl biteceğinin (kağıtta ne olacak, kişi hangi durumda olacak) yazılı olduğu bir tablo derlemek mümkündür. sonraki sayfanın hangi paketten alınacağı). Şimdi, bir kişinin eylemlerinin, büyük (ama sonlu) bir alfabeye ve çok sayıda (ama sonlu) iç duruma sahip bir Turing makinesinin çalışmasına karşılık geldiği zaten açıktır.

giriiş

1936'da Alan Turing, algoritma kavramını açıklığa kavuşturmak için soyut bir evrensel uygulayıcı önerdi. Soyutluğu, gerçek bir bilgisayar değil, mantıksal bir hesaplama yapısı olması gerçeğinde yatmaktadır. "Evrensel icracı" terimi, bu icracının başka herhangi bir icracıyı taklit edebileceği anlamına gelir. Örneğin, gerçek bilgisayarların gerçekleştirdiği işlemler evrensel bir yürütücü üzerinde simüle edilebilir. Sonuç olarak, Turing tarafından icat edilen hesaplamalı yapıya Turing makinesi adı verildi.

Bu ders çalışmasının amacı, Turing makinesini işlevsel programlama dili Haskell'de uygulayan bir program oluşturmaktır. Örneğin, bir ondalık sayıyı 2 ile çarpmak için tasarlanmış bir Turing makinesi uygulanacaktır.

Bu amaca ulaşmak için aşağıdaki görevleri çözmek gerekir: Turing makinesinin ilkelerini, yapısını inceleyin, algoritmik olarak çözülemeyen sorunları göz önünde bulundurun, bir veri yapısı seçin, uygulanan işlevleri tanımlayın ve ayrıca programdan örnekler verin.

Turing makinesinin temelleri

Turing makinesi adını, 1937'de soyut bir makine kullanarak algoritmaları resmi olarak belirlemek için bir yöntem öneren İngiliz matematikçi Alan Turing'den almıştır. İşin özü aşağıdaki gibidir. Her biri sonlu bir alfabeden bir karakter içerebilen hücrelere bölünmüş potansiyel olarak sonsuz bir bant vardır. Bir Turing makinesi, geçerli hücredeki bir karakteri okumanıza, bir hücreye bir karakter yazmanıza ve bitişik bir hücreye doğru sola veya sağa hareket ettirmenize izin veren bir okuma/yazma kafasına sahiptir. Makine ayrı ayrı, döngülerle çalışır ve her döngüde, sonlu sayıda olan olası durumlardan birindedir. Her çift (durum, görüntülenen sembol) için bir üçlü tanımlanır (yazılan karakter, baş hareketi, yeni durum). Çalışmaya başlamadan önce Turing makinesi başlangıç ​​durumundadır ve okuma-yazma kafası teybin en soldaki boş olmayan hücresini tarar. Böylece bir sonraki karaktere bakarak makine yeni bir karakter (belki aynısı) yazar, kafayı sola, sağa hareket ettirir veya yerinde kalır ve yeni bir duruma geçer veya aynı durumda kalır.

Bir Turing makinesi üç bölümden oluşur: bir şerit, bir okuma (yazma) kafası ve Şekil 1'de açıkça gösterilen bir mantıksal aygıt.

Bant, harici bir bellek görevi görür. Sınırsız (sonsuz) kabul edilir. Bu zaten Turing makinesinin bir model cihaz olduğunu gösteriyor, çünkü hiçbir gerçek cihaz sonsuz belleğe sahip olamaz.

Şekil 1 - Bir Turing makinesinin diyagramı

Turing makinesi keyfi sonlu bir alfabe A = (_, a1…an) ile çalışır - bu alfabeye harici denir. İçinde özel bir karakter tahsis edilmiştir - _, boş karakter olarak adlandırılır - onu herhangi bir hücreye göndermek, daha önce orada olan karakteri siler ve hücreyi boş bırakır. Bandın her hücresine yalnızca bir karakter yazılabilir. Bantta depolanan bilgiler, harici alfabede boş karakter dışında sonlu bir karakter dizisi ile temsil edilir.

Kafa her zaman bandın hücrelerinden birinin üzerinde bulunur. İş döngüler (adımlar) halinde gerçekleşir. Baş tarafından yürütülen komutlar sistemi son derece basittir: her döngüde, izlenen ai hücresindeki işareti aj işaretiyle değiştirir. Bu durumda, kombinasyonlar mümkündür:

1) аj = аi - izlenen hücrede işaretin değişmediği anlamına gelir;

2) ay? _, aj = _ - hücrede depolanan karakter boş bir karakterle değiştirilir, yani. silindi;

3) ai = _, aj? _ - boş bir işaret, boş olmayan bir işaretle değiştirilir (alfabede j rakamıyla), yani. bir işaret eklenir;

4) ay? ay? _ - bir karakterin diğeriyle değiştirilmesine karşılık gelir.

Böylece, Turing makinesinde son derece basit bir bilgi işleme talimatları sistemi uygulanmaktadır. Bu işlem komutları sistemi, bandı hareket ettirmek için son derece basit bir komut sistemi ile tamamlanır: bir hücre sola, bir hücre sağa ve yerinde kal, yani. komutun yürütülmesi sonucunda izlenen hücrenin adresi 1 değişebilir veya değişmeden kalabilir.

Bununla birlikte, bandın fiilen hareketi olmasına rağmen, genellikle başın görüntülenen bölüme göre bir kayması göz önünde bulundurulur. Bu nedenle bandı sola kaydırma komutu R (Sağ), sağa kaydır - L (Sol), kaydırma yok - S (Durdur) ile gösterilir. Özellikle kafanın yer değiştirmesinden bahsedeceğiz ve R, L ve S'yi hareketi için komutlar olarak ele alacağız.

Bu komutların basitliği, belirli bir hücrenin içeriğine erişmek gerekirse, yalnızca bir hücrenin ayrı ayrı vardiya zinciri aracılığıyla bulunması anlamına gelir. Tabii ki, bu, işleme sürecini önemli ölçüde uzatır, ancak hücre numaralandırma ve adrese göre atlama komutlarının kullanımından vazgeçmeyi mümkün kılar, örn. teorik açıdan önemli olan gerçekten temel adımların sayısını azaltır.

Bilgilerin işlenmesi ve bir işaret yazmak için komutların verilmesi ve ayrıca Turing makinesinde bandın kaydırılması, bir mantıksal birim (LU) tarafından gerçekleştirilir. LU, sonlu bir küme oluşturan ve Q =(q1…qm, q0) ile gösterilen durumlardan birinde olabilir ve q0 durumu işin tamamlanmasına karşılık gelir ve q1 başlangıçtır (başlangıç). Q, R, L, S karakterleri ile birlikte makinenin dahili alfabesini oluşturur. LU'nun iki giriş kanalı (ai, qi) ve üç çıkış kanalı (ai+1, qi+1, Di+1) vardır. Turing makinesinin LU şeması Şekil 2'de gösterilmiştir.

Şekil 2 - Turing makinesinin LU diyagramı

Şemayı şu şekilde anlamak gerekir: i. adımda, LU'nun bir girişine şu anda izlenen hücreden (ai) bir işaret uygulanır ve (qi) anında LU'nun durumunu gösteren bir işaret gönderilir. diğer girişe. Alınan işaret kombinasyonuna (ai, qi) ve mevcut işleme kurallarına bağlı olarak LU, ilk çıkış kanalı yoluyla izlenen hücreye yeni bir işaret (ai + 1) üretir ve gönderir, kafayı hareket ettirmek için bir komut verir (Di R, L ve S'den + 1) ve ayrıca bir sonraki duruma (qi+1) geçmek için komut verir. Böylece, Turing makinesinin temel adımı (döngüsü) şu şekildedir: kafa, izlenen hücreden bir karakter okur ve durumuna ve okunan karaktere bağlı olarak, hangi karakterin yazılacağını (veya silineceğini) ve ne hareketi yapmak. Aynı zamanda, kafa yeni bir duruma geçer. Böyle bir makinenin çalışma şeması Şekil 3'te gösterilmiştir.

Şekil 3 - Turing makinesinin işleyiş şeması

Bu şema, belleğin harici ve dahili olarak bölünmesini yansıtır. Dıştaki, belirtildiği gibi, sonsuz bir bant şeklinde sunulur - dış alfabenin sembollerinde kodlanmış bilgileri depolamak için tasarlanmıştır. Dahili bellek, geçerli döngü sırasında bir sonraki komutu depolamak için iki hücre ile temsil edilir: Q, LU'dan aktarılır ve bir sonraki durum depolanır (qi+1) ve D, kaydırma komutudur (Di+1). Geri besleme hattı aracılığıyla Q'dan qi+1 LU'ya girer ve D'den komut, gerekirse bandı bir konum sağa veya sola hareket ettiren aktüatöre gider.

Turing makinesinin çalıştığı genel kural, aşağıdaki gösterimle temsil edilebilir: qi aj > qi" aj" Dk, yani. aj sembolünü baş tarafından qi durumunda inceledikten sonra, aj" sembolü, baş qi" durumuna geçer, hücreye yazılır ve teyp Dk hareket eder. Her qi aj kombinasyonu için tam olarak bir dönüşüm kuralı vardır (yalnızca q0 için kural yoktur, çünkü bu duruma girdikten sonra makine durur). Bu, mantıksal bloğun, qi "aj" Dk çıktısının her bir giriş sinyali çiftiyle (qi aj bir ve yalnızca bir üçlü) eşlenen bir işlevi uyguladığı anlamına gelir - buna makinenin mantıksal işlevi denir ve genellikle şu şekilde sunulur: sütunları durum sembolleri ile gösterilen tablo (makinenin işlevsel diyagramı) ve dizeler - harici alfabenin karakterleri. Dış alfabenin karakterleri n ve LU durumlarının sayısı m ise, o zaman, dönüşüm kurallarının toplam sayısı n×m olacaktır.

Belirli bir Turing makinesi, A ve Q kümelerinin öğelerinin sıralanmasının yanı sıra LU'nun uyguladığı mantıksal işlevle, yani dönüşüm kuralları kümesi. Açıktır ki, sonsuz sayıda farklı A, Q kümeleri ve mantıksal fonksiyonlar olabilir, yani. ve ayrıca sonsuz sayıda Turing makinesi vardır.

Ayrıca, makine konfigürasyonu kavramını tanıtmak da gereklidir, örn. bandın tüm hücrelerinin durumları, LU'nun durumu ve başın konumu. Bir makinenin konfigürasyonunun, harici alfabenin herhangi bir sayıda sembolünü ve dahili olanın yalnızca bir sembolünü içerebileceği açıktır.

Çalışmaya başlamadan önce, boş bir teybe A alfabesiyle sonlu uzunlukta bir a sözcüğü yazılır; baş, a kelimesinin ilk sembolünün üzerinde ayarlanır, LU, q1 durumuna aktarılır (yani, ilk konfigürasyon q1a'ya benzer). Her yapılandırmada yalnızca bir dönüştürme kuralı uygulandığından, ilk yapılandırma makinenin sonraki tüm işlemlerini benzersiz bir şekilde belirler, örn. işin sona ermesine kadar tüm yapılandırma dizisi.

İlk yapılandırmaya bağlı olarak iki senaryo mümkündür:

1) sınırlı sayıda döngüden sonra, makine durdurma komutunda durur; bu durumda, çıktı bilgisine karşılık gelen son yapılandırma teypte görünür;

2) durak yok.

İlk durumda, verilen makinenin başlangıç ​​bilgisine uygulanabilir olduğu söylenir; ikincisinde ise değildir. Makinenin bir sonuç sağladığı girdi yapılandırmalarının tamamı, çözülmesi gereken bir problem sınıfı oluşturur. Açıkçası, çözülebilir olanlar sınıfına girmeyen bir problem için Turing makinesi kullanmak anlamsızdır.

Bir Turing varsayımı vardır: Belirli bir prosedür iyi tanımlanmışsa ve doğası gereği mekanikse, o zaman onu gerçekleştirebilecek bir Turing makinesinin olduğunu varsaymak oldukça mantıklıdır. Bir algoritma kavramının gevşek tanımını bir Turing makinesinin katı tanımıyla ilişkilendirdiği için kanıtlanamaz. Bir Turing fonksiyon diyagramı kullanılarak gerçekleştirilemeyen bir algoritma örneği verilebilirse, bu varsayım çürütülebilir. Ancak şimdiye kadar bilinen tüm algoritmalar Turing fonksiyon diyagramları aracılığıyla tanımlanabilir.

evrensel bir sanatçıyı incelemek için simülatör

Ne olduğunu?

Turing Makinesi simülatörü, 1936'da A. Turing tarafından bir algoritma kavramını açıklığa kavuşturmak için önerilen evrensel bir yürütücünün (soyut bilgisayar) eğitim modelidir. Turing'in tezine göre, herhangi bir algoritma bir Turing makinesi için program olarak yazılabilir. Turing makinesinin yeteneklerinde Post makinesi ve normal Markov algoritmalarına eşdeğer olduğu kanıtlanmıştır.

Turing makinesi bir taşıyıcı (okuma ve yazma kafaları) ve hücrelere bölünmüş sonsuz bir banttan oluşur. Bandın her hücresi, A=(a 0 ,a 1 ,…,a N ) alfabesinden bir karakter içerebilir. Herhangi bir alfabe, 0 veya Λ olarak gösterilen bir boşluk simgesi içerir. Komutları girerken boşluk, alt çizgi "_" ile değiştirilir.

Bir Turing makinesi, bir tablo tarafından kontrol edilen bir otomattır. Tablodaki satırlar, seçilen A alfabesinin sembollerine karşılık gelir ve sütunlar, Q=(q 0 ,q 1 ,…,q M ) otomatının durumlarına karşılık gelir. İşlemin başlangıcında, Turing makinesi q 1 durumundadır. Durum q 0 son durumdur: içine girdikten sonra otomat işini bitirir.

Bir ai sembolüne ve bir qj durumuna karşılık gelen tablonun her hücresinde, üç bölümden oluşan bir komut vardır:

1. A alfabesinden bir karakter;
2. hareket yönü: > (sağ),
3. yeni makine durumu

Haberler

1. Falina I.N. Okul bilgisayar bilimi dersinde (inf.1september.ru) "Turing Machine" konusu.
2. Mayer R.V. Post ve Turing makineleri (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Hot I.V. Turing makinesi ve Markov algoritmaları. Problem çözme, Moskova: Moskova Devlet Üniversitesi, 2006.
4. Beckman I.N. Bilgisayar Bilimi. Ders 7. Algoritmalar (profbeckman.narod.ru)
5. Solovyov A. Formülsüz ayrık matematik (lib.rus.ec)
6. Erşov S.S. Algoritma teorisinin unsurları, Chelyabinsk, SUSU Yayın Merkezi, 2009.
7. Varpakhovsky F.L. Algoritma teorisinin unsurları, M: Aydınlanma, 1970.
8. Vereshchagin NK, Shen A. Hesaplanabilir işlevler, M: MTsNMO, 1999.

Bununla ne yapmalı?

Programın üst kısmında, sorunun durumunu serbest biçimde girebileceğiniz bir editör alanı vardır.

Şerit, solunda ve sağında bulunan düğmeler kullanılarak sola ve sağa hareket ettirilir. Bir şerit hücreye çift tıklayarak (veya sağ tıklayarak) içeriğini değiştirebilirsiniz.

Menüyü kullanma Kurdele bandın durumunu dahili arabelleğe kaydedebilir ve bandı arabellekten geri yükleyebilirsiniz.

sahada Alfabe seçilen alfabenin karakterleri ayarlanır. Girilen karakterlere otomatik olarak bir boşluk eklenir.

Program, pencerenin altındaki tabloya yazılır. İlk sütun alfabetik karakterler içerir ve otomatik olarak doldurulur. İlk satır tüm olası durumları listeler. Tablonun üzerinde bulunan butonları kullanarak tablo (durum) sütunları ekleyebilir ve kaldırabilirsiniz.

Bir tablo hücresine komut girerken, önce yeni bir karakter, ardından geçişin yönü ve durum numarasını girmeniz gerekir. Bir karakter atlanırsa, varsayılan olarak değişmez. Durum numarası atlanırsa, otomatın durumu varsayılan olarak değişmez.

Tam sahada Bir yorumçözüme istediğiniz biçimde yorum girebilirsiniz. Çoğu zaman, Turing makinesinin her bir durumunun ne anlama geldiğini açıklarlar.

Program sürekli (F9) veya adım adım (F8) yürütülebilir. Şimdi yürütülecek olan komut yeşil bir arka planla vurgulanır. Yürütme hızı menü aracılığıyla ayarlanabilir Hız.

Bir Turing makinesi için görevler dosyalarda saklanabilir. Görev koşulu, alfabe, program, yorumlar ve bandın ilk durumu kaydedilir. Bir dosyadan bir görevi yüklerken ve onu bir dosyaya kaydederken, bandın durumu otomatik olarak ara belleğe yazılır.

Bir hata fark ederseniz veya öneri, yorum, şikayet, istek ve bildirimleriniz varsa, adresine yazın.

Teknik gereksinimler

Program, hattın işletim sistemleri altında çalışır. pencereler herhangi bir modern bilgisayarda.

Lisans

Program ticari olmayan kullanım için ücretsizdir. Programın kaynak kodu dağıtılmamıştır.

program ile birlikte gelir olduğu gibi”, yani yazar, manevi ve maddi kayıplar, ekipman arızası, fiziksel ve zihinsel yaralanmalar dahil olmak üzere kullanımının olası tüm sonuçlarından sorumlu değildir.

Programı başka web sitelerine yerleştirirken, kaynağa bir bağlantı gereklidir.

1. 1) diğer Web sitelerinde materyal yayınlamak da dahil olmak üzere herhangi bir biçimde materyal yayınlamak;
2. 2) eksik veya değiştirilmiş materyallerin dağıtımı;
3. 3) materyallerin herhangi bir ortamdaki koleksiyonlara dahil edilmesi;
4. 4) malzemelerin satışından veya diğer kullanımlarından ticari fayda elde etmek.

Materyalleri indirmek, bu lisans sözleşmesinin şartlarını kabul ettiğiniz anlamına gelir.

İndirmek

Arşivi paketinden çıkardıktan sonra program çalışır durumdadır ve herhangi bir ek kurulum gerektirmez.

1. Turing makinesinin tanımı. 3

1.1 Algoritma olarak bir Turing makinesinin özellikleri. 5

2. Algoritmaların karmaşıklığı. 7

2.1 Problemlerin karmaşıklığı.. 9

3. Turing makinesi ve algoritmik olarak çözülemeyen problemler.. 12

Çözüm. 16

Referanslar.. 18

giriiş

Bir Turing makinesi çok basit bir bilgi işlem cihazıdır. Hücrelere bölünmüş sonsuz uzunlukta bir banttan ve bant boyunca hareket eden ve karakterleri okuyup yazabilen bir kafadan oluşur. Ayrıca, Turing makinesi, sıfırdan bir maksimum değere kadar bir tamsayı olarak ifade edilebilen bir durum gibi bir özelliğe sahiptir. Duruma bağlı olarak, bir Turing makinesi üç şeyden birini yapabilir: bir hücreye bir karakter yazmak, bir hücreyi sağa veya sola hareket ettirmek ve dahili durumu ayarlamak.

Turing makinesi son derece basittir, ancak hemen hemen her programı çalıştırabilir. Tüm bu eylemleri gerçekleştirmek için, banttan okunan mevcut durumların ve karakterlerin çeşitli kombinasyonlarıyla ne yapılacağını belirten özel bir kurallar tablosu sağlanır.

1947'de Alan Turing, tanımı bir "evrensel Turing makinesi" olarak tanımlayacak şekilde genişletti. Daha sonra, belirli problem sınıflarını çözmek için, bir değil birkaç görevi yerine getirmeyi mümkün kılan çeşitliliği tanıtıldı.

1. Turing makinesinin tanımı

Bu çalışmanın yaratılışının tarih öncesi, 1900'de Paris'teki Uluslararası Matematikçiler Kongresi'nde David Hilbert tarafından çözülmemiş matematik problemlerinin formüle edilmesiyle bağlantılıdır. Bunlardan biri, Hilbert'in daha sonra "karar verebilirlik sorunu" olarak tanımladığı, sıradan aritmetiğin aksiyomları sisteminin tutarlılığını kanıtlama sorunuydu - belirli bir ifadenin resmi mantık dilinde tatmin edilebilirliğini belirlemek için genel bir yöntem bulmak.

Turing'in makalesi bu soruna bir yanıt verdi - Hilbert'in ikinci sorununun çözülemez olduğu ortaya çıktı. Ancak Turing'in makalesinin önemi, yazıldığı sorunun çok ötesine geçti.

İşte John Hopcroft'un bu çalışmasının bir açıklaması: "Hilbert sorunu üzerinde çalışan Turing, bir yöntem kavramının net bir tanımını vermek zorundaydı. Bir yöntemin bir tür algoritma olarak sezgisel fikrinden başlayarak, yani. yaratıcı müdahale olmadan mekanik olarak gerçekleştirilebilen bir prosedür , bu fikrin hesaplama sürecinin ayrıntılı bir modeli şeklinde nasıl somutlaştırılabileceğini gösterdi.Sonuçta, her algoritmanın bir basit diziye bölündüğü hesaplama modeli , temel adımlar, daha sonra Turing makinesi olarak adlandırılan mantıksal bir yapıydı. "

Turing makinesi, sonlu otomat modelinin bir uzantısıdır; şu anda görüntülenen hücreden sol veya sağ komşusuna hareket etme (taşıma) yeteneğine sahip potansiyel olarak sonsuz bir bellek içeren bir uzantıdır.

Resmi olarak, bir Turing makinesi aşağıdaki gibi tanımlanabilir. Verelim:

Turing makinesinin olabileceği sonlu bir durumlar kümesi - Q;

sonlu bant sembolleri seti - Г;

Kartezyen çarpım Q x Г'den (makine qi durumundadır ve gi sembolünü inceler) bir çifti Kartezyen çarpım Q x Г x'in (L) üçlüsüne eşleyerek verilen δ işlevi (geçiş işlevi veya program) , R) (makine qi durumuna geçer, gi karakterini gj karakteriyle değiştirir ve bir bant karakteri sola veya sağa hareket eder) – Q x G --> Q x G x (L,R)

G-->e'den bir karakter (boş);

Σ є Г - -> alt kümesi, bandın giriş sembollerinin bir alt kümesi olarak tanımlanır ve e є (Г - Σ);

durumlardan biri - q0 є Q, makinenin başlangıç ​​durumudur.

Çözülmesi gereken problem, bant üzerine Σ є Г - Si є Σ kümesinden sonlu sayıda sembol yazılarak verilir:

eS1S2S3S4... ... ...Sne

bundan sonra makine başlangıç ​​durumuna aktarılır ve kafa en soldaki boş olmayan sembole (q0,w) ayarlanır - bundan sonra belirtilen geçiş işlevine göre (qi,Si) - -> (qj, Sk, L veya R), makine görüntülenecek karakterleri değiştirmeye başlar, kafayı sağa veya sola hareket ettirir ve geçiş fonksiyonları tarafından belirtilen diğer durumlara geçer.

(qi,Si) çifti için geçiş fonksiyonu tanımlanmamışsa makine durur.

Alan Turing, kelimenin sezgisel anlamında herhangi bir algoritmanın eşdeğer bir Turing makinesi tarafından temsil edilebileceğini öne sürdü. Bu varsayım, Church-Turing tezi olarak bilinir. Her bilgisayar bir Turing makinesini simüle edebilir (hücrelerin üzerine yazma, karşılaştırma ve makinenin durumundaki değişiklikleri hesaba katarak başka bir komşu hücreye taşıma işlemleri). Sonuç olarak, algoritmaları herhangi bir biçimcilikte modelleyebilir ve bu tezden, tüm bilgisayarların (güç, mimari vb. ne olursa olsun) algoritmik problemleri çözmenin temel olasılığı açısından eşdeğer olduğu sonucu çıkar.

1.1 Algoritma olarak bir Turing makinesinin özellikleri

Bir Turing makinesi örneğinde, algoritmaların özellikleri iyi izlenir. Öğrencilerden bir Turing makinesinin bir algoritmanın tüm özelliklerine sahip olduğunu göstermelerini isteyin.

ayrıklık Turing Makinesi, (k + 1)-inci adımın ne olacağını belirleyen her adım olduğu için, her adım yürütüldükten sonra ancak (k + 1)-inci adıma gidebilir.

netlik Her adımda hücreye alfabeden bir sembol yazılır, otomat bir hareket yapar (L, P, N) ve Turing makinesi açıklanan durumlardan birine girer.

kararlılık. Turing makinesi tablosunun her hücresinde yalnızca bir seçenek kaydedilir. Her adımda, sonuç benzersiz bir şekilde tanımlanır; bu nedenle, sorunu çözmek için adımların sırası benzersiz bir şekilde tanımlanır, yani. Turing makinesi aynı giriş word'ü ile beslenirse, çıkış word'ü her seferinde aynı olacaktır.

Yeterlik. İçerik açısından, her adımın sonuçları ve tüm adım dizisi benzersiz bir şekilde belirlenir; sonlu sayıda adımda, problemin sorusunun cevabı elde edilecektir.

Toplu karakter. Her Turing makinesi, alfabedeki tüm geçerli kelimeler üzerinden tanımlanır ve bu, kütle özelliğidir. Her Turing makinesi, bir sınıf problemi çözmek için tasarlanmıştır, örn. Her görevin kendi (yeni) Turing makinesi vardır.

2. Algoritmaların karmaşıklığı

Bir algoritmanın karmaşıklığı, onu yürütmek için gereken hesaplama gücü ile belirlenir. Bir algoritmanın hesaplama karmaşıklığı genellikle iki terimle ölçülür: T (zaman karmaşıklığı) ve S (uzay karmaşıklığı veya bellek gereksinimleri). Hem T hem de S genellikle n'nin fonksiyonları olarak temsil edilir; burada n, girdinin boyutudur. (Karmaşıklığı ölçmenin başka yolları da vardır: rastgele bitlerin sayısı, iletişim kanalının genişliği, veri miktarı, vb.)

Genellikle, bir algoritmanın hesaplama karmaşıklığı "Büyük O" gösterimi kullanılarak ifade edilir, yani hesaplama karmaşıklığının bir büyüklük sırası ile tanımlanır. Bu basitçe, n ile en hızlı büyüyen karmaşıklık genişlemesinin terimidir, tüm düşük dereceli terimler göz ardı edilir. Örneğin, belirli bir algoritmanın zaman karmaşıklığı 4n2+7n+12 ise, hesaplama karmaşıklığı n2 mertebesindedir ve O(n2) olarak yazılır.

Bu şekilde ölçülen zaman karmaşıklığı uygulamadan bağımsızdır. Çeşitli komutların tam yürütme zamanını veya çeşitli değişkenleri temsil etmek için kullanılan bit sayısını ve hatta işlemcinin hızını bilmenize gerek yoktur. Bir bilgisayar diğerinden yüzde 50 daha hızlı olabilir ve üçüncüsünün veri yolu iki kat daha geniş olabilir, ancak algoritmanın büyüklük sırasına göre ölçülen karmaşıklığı değişmez. Bu, hile yapmak değildir, bu kitapta açıklananlar kadar karmaşık algoritmalarla uğraşırken, karmaşıklığın büyüklük sırasına kıyasla diğer her şey ihmal edilebilir (sabit bir faktöre kadar).

Bu gösterim, girdi boyutunun zaman ve bellek gereksinimlerini nasıl etkilediğini görmenizi sağlar. Örneğin, eğer T = O(n), o zaman girdiyi iki katına çıkarmak, algoritmanın yürütme süresini de iki katına çıkaracaktır. T=O(2n) ise, giriş verilerine bir bit eklenmesi algoritmanın yürütme süresini iki katına çıkaracaktır.

Tipik olarak, algoritmalar zaman veya uzay karmaşıklığına göre sınıflandırılır. Karmaşıklığı n: 0(1)'e bağlı değilse, bir algoritmaya sabit denir. Zaman karmaşıklığı O(n) ise bir algoritma doğrusaldır. Algoritmalar ikinci dereceden, kübik vb. olabilir. Tüm bu algoritmalar polinomdur, karmaşıklıkları O(m)'dir, burada m bir sabittir. Polinom zaman karmaşıklığına sahip algoritmalara polinom zaman algoritmaları denir

Karmaşıklığı O(tf(n))'ye eşit olan, t'nin 1'den büyük bir sabit olduğu ve f(n)'nin n'nin bir polinom fonksiyonu olduğu algoritmalara üstel denir. Üstel algoritmaların karmaşıklığı O(cf(n)) olan, c'nin bir sabit olduğu ve f(n)'nin bir sabitten daha hızlı ama doğrusal bir fonksiyondan daha yavaş büyüdüğü alt kümesine süperpolinom denir.

İdeal olarak, bir kriptograf, tasarlanmış bir şifreleme algoritmasını kırmak için en iyi algoritmanın üstel zaman karmaşıklığına sahip olduğunu iddia etmek ister. Uygulamada, hesaplama karmaşıklığı teorisinin mevcut durumu göz önüne alındığında yapılabilecek en güçlü ifadeler, "belirli bir kriptosistemi kırmak için bilinen tüm algoritmaların süperpolinom zaman karmaşıklığına sahip olduğu" biçimindedir. Yani, bildiğimiz saldırı algoritmaları süper polinom zaman karmaşıklığına sahiptir, ancak polinom zaman karmaşıklığına sahip bir saldırı algoritmasının keşfedilemeyeceğini kanıtlamak henüz mümkün değildir. Hesaplama karmaşıklığı teorisinin gelişimi, bir gün, polinom açılış süresine sahip algoritmaların varlığının matematiksel kesinlik ile hariç tutulabileceği algoritmaların yaratılmasına izin verebilir.

Turing Makinesi, 20. yüzyılın en ilgi çekici ve heyecan verici entelektüel keşiflerinden biridir. Herhangi bir bilgisayar görevini gerçekleştirmek için yeterince genel olan basit ve kullanışlı soyut bir bilgi işlem modelidir (bilgisayar ve dijital). 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 edilmesi de dahil olmak üzere, dijital bilgisayarlar ve matematik hakkında daha derin bir anlayışa yol açmıştır.

Alan Turing, bir bilgisayarla aynı temel yeteneklere sahip olacak mekanik bir cihazın en ilkel modelini tanımlamaya çalıştı. Turing, makineyi ilk olarak 1936'da Proceedings of the London Mathematical Society'de çıkan "On Computable Numbers with an Application to the Decidability Problem" adlı kitabında tanımladı.

Bir Turing makinesi, içinden bir kağıt bant geçen bir okuma/yazma kafasından (veya "tarayıcıdan") oluşan bir bilgi işlem aygıtıdır. Bant, her biri tek bir sembol - "0" veya "1" taşıyan karelere bölünmüştür. Mekanizmanın amacı, hem bir giriş ve çıkış aracı hem de hesaplamaların ara aşamalarının sonuçlarını depolamak için çalışan bir hafıza görevi görmesidir. Cihazın içeriği 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 program, veri okumak ve yazmak için bir tarayıcı kafasıdır. Herhangi bir anda birçok durumdan 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. Durum q0 pasif olarak adlandırılır. Cihazın kendisine çarptığında çalışmasını sonlandırdığına inanılıyor. Durum q1, ilk durum olarak adlandırılır - makine, içinde başlangıçta olmak üzere hesaplamalarına başlar. Girilen kelime, her pozisyonda arka arkaya bir harf banda yerleştirilir. Her iki tarafında da sadece boş hücreler var.

mekanizma nasıl çalışır

Turing makinesinin bilgi işlem cihazlarından temel bir farkı vardır - depolama cihazı sonsuz bir teybe sahipken, dijital cihazlar için bu tür bir cihaz belirli bir uzunlukta bir şeride sahiptir. Her görev sınıfı, yalnızca bir inşa edilmiş 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. Taşıma sırasında, giriş verisi içermeyen konumları dolduran boş bir öğe tahsis edilir. Turing makinesi için algoritma, kontrol cihazı için geçiş kurallarını tanımlar. Yazma-okuma kafasına şu parametreleri ayarlarlar: hücreye yeni bir karakter yazmak, yeni bir duruma geçiş, bant boyunca sola veya sağa hareket etmek.

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, yalnızca bir önceki tamamlandıktan sonra n+1 sonraki adıma 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 karşılık gelir ve her aşamada eylemler ve bunların uygulanma sırası açıktır. Yeterlik. Her adım için kesin sonuç Turing makinesi tarafından belirlenir. Program algoritmayı yürütür ve sınırlı sayıda adımda q0 durumuna geçer. Toplu karakter. Her cihaz, alfabede yer alan izin verilen kelimeler üzerinden tanımlanır. Turing Makinesi Fonksiyonları Algoritmaların çözümünde genellikle bir fonksiyonun gerçeklenmesi gerekir. Hesaplama için bir zincir yazma olasılığına bağlı olarak, fonksiyona algoritmik olarak karar verilebilir veya karar verilemez denir. Doğal veya rasyonel sayılar kümesi olarak, bir makine için sonlu bir N alfabesindeki sözcükler, B kümesinin sırası dikkate alınır - B = (0.1) ikili kod alfabesi çerçevesindeki sözcükler. Ayrıca, hesaplamanın sonucu, algoritma "donduğunda" ortaya çıkan "tanımsız" değeri dikkate alır. İşlevi gerçekleştirmek için sonlu alfabede resmi bir dil 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 dış alfabenin sembollerini ve otomatın olası iç durumlarının - iç alfabenin değerlerini içerdiği tablolarda düzenlenir. Tablo verileri, Turing makinesinin kabul ettiği komutlardır. Problem çözme şu şekilde ilerler: kafanın o anda üzerinde bulunduğu hücrede okuduğu harf ve otomat kafasının dahili durumu, hangi komutların yürütülmesi gerektiğini belirler. Spesifik olarak, böyle bir komut, tabloda bulunan dış alfabe ve iç alfabe sembollerinin kesişme noktasında 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ımlamak gerekir. dış alfabe Bu, A işaretiyle gösterilen ve bileşenlerine harfler adı verilen sonlu bir semboller dizisidir. 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, problemleri çö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ının kümesi dahili alfabedir. Q=(q1, q2...) gibi bir harf tanımına sahiptir. Bu konumlardan biri - q1 - ilk konum, yani programı başlatan konum olmalıdır. Diğer bir gerekli unsur, son durum olan, yani programı sonlandıran ve cihazı durma konumuna getiren durum q0'dır.

Atlama tablosu.

Bu bileşen, makinenin geçerli durumuna ve okunmakta olan karakterin değerine bağlı olarak aygıt taşıyıcı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ımda aşağıdaki eylem sırasını gerçekleştiren bir program tarafından kontrol edilir: Harici alfabenin bir karakterini, boş da dahil olmak üzere bir konuma yazmak, boş da dahil olmak üzere içinde bulunan öğeyi değiştirmek bir. Bir adım hücresini sola veya sağa taşıyın. Dahili durumunuzu değiştirin. Bu nedenle, her bir karakter veya konum çifti için program yazarken, üç parametreyi doğru bir şekilde tanımlamak gerekir: ai - seçilen alfabe A'dan bir öğe, taşıma yönü kaydırma ("←" sola, "→" sola sağ, "nokta" - hareket yok) ve qk - cihazın yeni durumu Örneğin, komut 1 "←" q2, "karakteri 1 ile değiştir, taşıma kafasını sola bir adım hücreye taşı ve duruma atla" değerine sahiptir q2".