Turing makinelerinin bileşimi örnekleri. Turing makinesindeki fonksiyonların doğru hesaplanabilirliği

Turing makinesi (MT) soyut bir icracıdır (soyut hesaplama makinesi).

Algoritma kombinasyonları, belirli birkaç algoritmadan yeni algoritmalar oluşturmak için kullanılan belirli yöntemlere verilen addır.

Algoritma kombinasyonlarına ilişkin teoremler, genel algoritma teorisinin önemli bir bölümünü oluşturur. Kanıtlandıktan sonra, karmaşık ve hantal algoritmaların fizibilitesini, onları tanımlayan devreleri gerçekten yazmadan daha sonra doğrulamayı mümkün kılarlar.

Bir Turing makinesine yönelik algoritma kombinasyonları, Turing makinelerindeki işlemlerle açıklanmaktadır.

1. Kompozisyon işlemi.

M 1 ve M 2 aynı dış alfabe A'ya (a 0 , a 1 ,..., a p ) sahip Turing makineleri olsun. Durum kümelerini sırasıyla Q1 "(q 0,q 1,...,q n) ve Q2 "(q 0",q 1",...,q m") olarak gösterelim.

Tanım.

M 1 ve M 2 makinelerinin bir bileşimi, M=M 1 ×M 2 olarak gösterilen bir makinedir; programı A alfabesine, Q« (q 0,q 1,...,q n,q) durum kümesine sahiptir. n+1,... ,q n+m) ve M 1 ve M 2 makinelerinin programlarından şu şekilde elde edilir: M 1 makinesinin programının her yerinde, burada q 1 simgeli “üçlüler” vardır ( M 1 makinesinin son durumu), q 0" sembolü ile değiştirilir (M 2 makinesinin başlangıç ​​durumu); M 1 ve M 2 makinelerinin programlarındaki diğer tüm semboller değişmeden kalır (sonunda, geriye M makinesinin tüm durumlarını yeniden numaralandırmak kalıyor: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m")).

Kompozisyon bir M1 makinesi olarak "çalışmaya" başlar, ancak M1 makinesinin durması gerektiği durumlarda, q1'in q0" ile değiştirilmesi nedeniyle M2 makinesinin programına geçer. Açıkçası, kompozisyon işlemi ilişkiseldir ancak değişmeli değildir.

Çalışması T1 ve T2 makinelerinin sıralı çalışmasına eşdeğerdir.

Şekilde n=1 ve m=1 için süperpozisyon operatörünü uygulayan Turing makinelerinin bir bileşimi gösterilmektedir.

Resim 1.

Tanım.

Turing makinesi M'nin yinelenmesine makine adı verilecek

2. Dallanma işlemi.

M 1, M 2 ve M 3 aynı dış alfabe A« (a 0, a 1,..., a i,..., a j,..., a p) ve buna göre aşağıdaki kümelere sahip Turing makineleri olsun. durumları: Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. .,ql").

Tanım.

Turing makineleri M 1, M 2 ve M3 üzerinde dallanma işleminin sonucuna Turing makinesi M adı verilir ve programı M 1, M 2 ve M 3 makinelerinin programlarından şu şekilde elde edilir: programı M1 makinesi yazılır, ardından M 2 ve M 3 makinelerinin programları atanır. M1 makinesinin son durumu q1'de a i sembolü gözlenirse, kontrol M2 makinesine aktarılır, yani. q 1 sembolü, q 0" sembolü ile değiştirilir ve M 2 makinesi çalışmaya başlar. M 1 makinesinin q 1 son durumunda a j sembolü gözlenirse, kontrol M 3 makinesine aktarılır, yani q 1 sembolü değiştirilir q 0" sembolü ile makine M3 çalışmaya başlar. M 1 ve M 2 makinelerinin programlarındaki diğer tüm semboller değişmeden kalır. M makinesi işini son q 1 durumunda tamamlar (sonuç olarak, M makinesinin durumlarının uçtan uca yeniden numaralandırılmasını gerçekleştirmeye devam eder).

Turing makineleri M 1, M 2 ve M3'teki dallanma işleminin sonucu şu şekilde gösterilir:

İki harfli Turing makineleri için (iki harfli alfabeye sahip Turing makineleri), keyfi Turing makineleri M1, M2 ve M3 üzerindeki dallanma işlemi şu şekilde gösterilir:

onlar. M1 makinesi q 1 durumunda çalışırken, a 0 sembolü gözlenirse, kontrol M2 makinesine, aksi halde M3 makinesine aktarılır.

3. Döngü işlemi.

M, A« (a 0 ,a 1 ,...,a p ) alfabesine ve Q« (q 0 ,q 1 ,...,q n ) durum kümesine sahip bir Turing makinesi olsun.

Tanım.

Döngü işleminin sonucuna Turing makinesi adı verilecek ve (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,...,n)

programı M makinesinin programından q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. komutunun sonucunda q 1 sembolünün değiştirilmesiyle elde edilen programdır. .p, q s simgesiyle.

2.4 Turing makinesi çeşitleri

Turing makinesi modeli genişletilebilir. Turing makinelerini isteğe bağlı sayıda bant ve çeşitli kısıtlamalara sahip çok boyutlu bantlar olarak değerlendirebiliriz. Ancak bu makinelerin tamamı Turing'dir ve sıradan bir Turing makinesi tarafından modellenmiştir.

Böyle bir eşdeğerliğe örnek olarak, herhangi bir MT'nin yarı sonsuz bir bant üzerinde çalışan bir MT'ye indirgenmesini düşünün.

Teorem: Herhangi bir Turing makinesi için yarı sonsuz bantta çalışan eşdeğer bir Turing makinesi vardır.

Kanıt:

Yu G. Karpov'un kanıtını ele alalım. Bu teoremin kanıtı yapıcıdır, yani herhangi bir Turing makinesi için beyan edilen özelliğe sahip eşdeğer bir Turing makinesinin oluşturulabileceği bir algoritma vereceğiz. Öncelikle MT çalışma bandının hücrelerini rastgele numaralandırıyoruz, yani bant üzerinde yeni bir bilgi konumu belirliyoruz:

Resim 1.

Daha sonra hücreleri yeniden numaralandırıyoruz ve “*” sembolünün MT sözlüğünde bulunmadığını varsayacağız:

Resim 1.

2.5 Turing'in hesaplanabilirliği ve karar verilebilirliği

Özyinelemeli fonksiyonlar, Turing makineleri veya normal Markov algoritmaları kullanılarak hesaplanabilen fonksiyon sınıflarının çakıştığı yukarıda kanıtlanmıştır. Bu, "hesaplamalı algoritma" kavramını açıklama yönteminden bağımsız olarak düşünmemize olanak tanır. Farklılıklar yalnızca algoritmik nesnelerin kullanımında görülmektedir. Özyinelemeli işlevler için nesneler sayılar ve sayısal işlevlerse ve hesaplama süreci süperpozisyon, özyineleme, minimizasyon ve yineleme operatörleri tarafından belirtiliyorsa, o zaman Turing makineleri için bu tür nesneler harici ve dahili belleğin alfabelerinin sembolleridir ve hesaplama süreç çıkışı, geçişi ve kafayı hareket ettirmeyi kullanan bir protokolle belirtilir. Normal bir Markov algoritması için, bu tür nesneler kelimeler veya sembol dizileridir ve hesaplama süreci, orijinal sembol dizisinin kompozisyonunu ve yapısını istenen sonuca dönüştüren ikame kuralları veya ürünlerle belirlenir.

Aritmetik (sayısal) bir fonksiyon, değer aralığı N kümesinin bir alt kümesi olan ve tanım alanı N kümesinin bir elemanı olan bir işlevdir.

Algoritmik problemler için tipik bir durum, x 1, x 2 argümanlarının tamsayı değerlerine bağlı olarak f(x 1, x 2, ..., x n) sayısal fonksiyonunu hesaplamak için bir algoritma bulmanız gerektiğidir. , ..., xn.

Bağımsız değişkenlerinin herhangi bir değer kümesinin, işlevin değerini hesaplamasına izin veren (veya işlevin belirli bir kümede tanımlanmadığını gösteren) bir algoritma varsa, f:N n →N işlevini hesaplanabilir olarak adlandırırız. Hesaplanabilir bir fonksiyonun tanımı sezgisel bir algoritma konseptini kullandığından, "hesaplanabilir fonksiyon" terimi yerine sıklıkla "sezgisel hesaplanabilir fonksiyon" terimi kullanılır. Dolayısıyla, eğer probleme karşılık gelen aritmetik fonksiyon sezgisel olarak hesaplanabilirse, büyük bir problemin bir çözümü vardır.

Bir f(x 1 , x 2 , …, x n) fonksiyonu, verilen k 1 , k 2 , …, k n argüman değerleri için f(k 1 , k 2 , …, k n) mevcut bazı mekanik prosedürleri (algoritma) kullanarak.

Algoritma kavramını açıklığa kavuşturmak yerine "hesaplanabilir fonksiyon" kavramını açıklığa kavuşturmayı düşünebiliriz. Genellikle aşağıdaki şemaya göre ilerlerler:

1. Kesin olarak tanımlanmış bir fonksiyon sınıfı tanıtılmıştır.

2. Bu sınıftaki tüm fonksiyonların hesaplanabilir olduğundan emin olun.

3. Hesaplanabilir işlevler sınıfının tanıtılan işlevler sınıfıyla çakıştığı hipotezini (tezini) kabul edin.

Bir fonksiyonu hesaplayan bir algoritma varsa, bu fonksiyona hesaplanabilir denir. Hesaplanabilirlik, hesaplanan fonksiyon ve algoritmaya göre değişmeyen, algoritma teorisinin temel kavramlarından biridir. Hesaplanabilir bir fonksiyon ile bir algoritma arasındaki fark, fonksiyonun tanımı ile bağımsız argümanların değerleri göz önüne alındığında değerlerini hesaplama şekli arasındaki farktır.

Turing'in tezi. Herhangi bir sezgisel algoritma, bazı Turing makineleri kullanılarak uygulanabilir.

Turing'in tezinden, algoritmik problemler ortaya çıkarsa, bunların Turing makinelerinin yapısına, yani yeterince resmileştirilmiş bir algoritma kavramına dayanarak çözülmesi gerektiği sonucu çıkar. Üstelik algoritmik problemlerde genellikle bir algoritma oluşturmaktan değil, özel olarak oluşturulmuş bazı fonksiyonların hesaplanabilirliğinden bahsediyoruz.

Bu durumlarda, 0'ın boş karakter olduğu alfabeyi (0,|) kullanmanın yeterli olduğuna dikkat edilmelidir. Örneğin 0 dahil doğal sayılar bu alfabede şu şekilde kodlanmıştır: 0 - |; 1 - ||; 2 -

N - ||…| (n + 1 kez). Kısmi bir sayısal n-yerel fonksiyon f(x1, x2, ..., xn), eğer onu aşağıdaki anlamda hesaplayan bir M makinesi varsa, Turing hesaplanabilir olarak adlandırılır: 1. Eğer argüman değerleri kümesi ise f fonksiyonunun tanım alanına aittir, ardından M makinesi, 0 |x1+1 0 |x2+1 ... 0 |xn q1 | konfigürasyonunda çalışmaya başlar, burada |x = ||... | (x kere) ve en sağdaki karakter algılanır, durur ve 0|yq0 | konfigürasyonunda sonlanır, burada y = f(x1, x2, …, xn). 2. Eğer argüman değerleri kümesi f fonksiyonunun tanım alanına ait değilse, bu durumda ilk konfigürasyonda çalışmaya başlayan M makinesi sonsuz olarak çalışır, yani son duruma ulaşmaz. Turing makinesi, bir algoritmanın kesin resmi tanımıdır. Bu kavramı kullanarak algoritmik problemlerin çözülebilirliği veya çözülemezliği kanıtlanabilir. Tek bir problem sınıfına ait bir problemi çözecek bir hesaplamalı algoritma bulunursa, o zaman problemin algoritmik olarak çözülebilir bir problem olduğu söylenir. Başka bir deyişle, bir hesaplamanın hesaplanabilirliği veya etkililiği için bir ön koşul, onun algoritmik çözülebilirliğidir. Bu anlamda “karar verilebilirlik” kavramı algoritma teorisinde de temel bir kavramdır. Üç tip modelin analizi, ayrıklık, determinizm, kütle karakteri ve etkililiğin temel özelliklerinin çeşitli tanımlama yöntemleri için değişmeden kaldığını göstermektedir: Ayrıklık özelliği: algoritma, adımlarla gerçekleştirilen bireysel temel eylemlerden oluşur; algoritmik bir süreci oluşturan temel adımlar kümesi sonlu ve sayılabilir. Deterministik özellik: Her adımdan sonra algoritmik sürecin sonraki adımlarının nasıl ve hangi sırayla gerçekleştirileceğine ilişkin kesin talimatlar verilir. Kütle özelliği: Belirli bir türdeki ve belirli bir problem sınıfındaki birçok algoritmik nesne için bir algoritmanın kullanılmasına izin verilir. Etkililik özelliği: İstenilen sonucu gösteren sonlu sayıda adımdan sonra algoritmik sürecin durdurulması zorunludur. Ancak tez, kesin olmayan Turing hesaplanabilirlik kavramıyla sezgisel olarak hesaplanabilir bir fonksiyon kavramıyla bağlantılı olduğundan kanıtlanamaz.

KENDİNE UYGULANABİLİRLİK SORUNU

Turing makinesinin tanımına göre bu üçlü T= , burada A- alfabe, Q - makinenin iç durumları, Q- bir makineyi diğerinden ayıran bir program. Genel durumda (tüm makineler için), program örneğin şöyle görünebilir:

P: ki A bir j A ® q r A gibi A S t A , a = 1, 2, …, k , Nerede S1- R, S2-L, S3- C . (*)

Bu durumda bazı ortak alfabelerin olduğunu varsayabiliriz. 0 Ve Soru 0 karakterlerin yazıldığı yer A Ve Q tüm Turing makineleri için. Daha sonra semboller ki A, bir j A, q r A, gibi A, S t A alfabelerin sembolleridir 0 Ve Soru 0.

Bu yaklaşım, tüm Turing makinelerinin numaralandırılmasına, yani her makineye, onu diğer makinelerden ayırt edebilecek, bu makineye özgü belirli bir numara (kod) atanmasına olanak tanır. Burada numaralandırma yöntemlerinden birini ele alacağız.

Turing makinelerinin Gödel numaralandırması. İzin vermek s 1 , s 2 , s 3 , ... - artan sırada düzenlenmiş bir asal sayı dizisi, örneğin, 2, 3, 5, 7, 11, 13, ...

Programlı Turing makinesi numarası (*) aranan numara

n(T) = .

Örnek

Bir işlevi uygulayan bir makine S(X)= x + 1 , alfabede bir program var {0,  } . Bu programın sayısı dikkate alındığında 0 = 0 , 1= | bir sayı olacak:.

n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .

Açıkçası, tüm doğal sayılar Turing makinesi sayıları değildir. Öte yandan eğer N – belirli bir makinenin genel alfabedeki numarası, ardından programı bu numaradan benzersiz bir şekilde geri yüklenebilir.

Araba T, kelimeye uygulanabilir N(T)(yani kendi numaranızın koduna), kendi kendine uygulanabilir denir .

Hem kendi kendine uygulanabilen makineler hem de kendi kendine uygulanamayan makineler yapmak mümkündür. Örneğin, verilen örnekteki makine kendi kendine uygulanabilir. Araba T Programın doğru kısımlarında (tablonun gövdesinde) durdurma simgesi olmayan, hiçbir kelimeye ve dolayısıyla kelimeye uygulanamaz. N(T).

Kendi kendine uygulanabilirlik sorunuşu şekildedir: herhangi bir Turing makinesi verildiğinde, onun kendi kendine uygulanabilir olup olmadığını belirleyecek bir algoritmayı belirtmek.

Turing Tezine göre böyle bir algoritmanın Turing makinesi formunda aranması gerekir. Bu makine, tüm Turing makinelerinin sayı kodlarına uygulanabilir olmalı ve test edilen makinelerin kodlarının işlenmesinin sonucuna bağlı olarak farklı son konfigürasyonlara sahip olmalıdır.

Mesela bu arabayı T koda uygulandı N(T * ) . Eğer araba T * kendi kendine uygulanabilir, ardından son makine konfigürasyonu T benziyor A" q 0 | B" ve eğer araba T * kendi kendine uygulanamıyorsa makinenin son konfigürasyonu T benziyor A" q 0 0B ". Burada a", B", a", B"- kelimeler.

Teorem Kendi kendine uygulanabilirlik sorunu algoritmik olarak karar verilemez, yani bu sorunu yukarıdaki anlamda çözen bir Turing makinesi yoktur.

Teoremden, kendi kendine uygulanabilirlik sorununu çözen genel bir algoritma olmadığı sonucu çıkar. Belirli özel durumlarda bu tür algoritmalar mevcut olabilir.

Başlangıç ​​kelimesine uygulanabilirlik probleminin karar verilemezliğini kanıtlamak için bu teoremin sonuçlarını kullanalım.

İlk kelimeye uygulanabilirlik sorunu şu şekildedir: makineye göre bir algoritma oluşturun T ve kelime X kurulacak, uygulanabilir makine T Bu arada X ya da değil (aksi halde durma sorunu vardır).

Turing makineleri açısından, kendi kendine uygulanabilirlik probleminin formülasyonuna benzer şekilde, bu problem şu şekilde formüle edilmiştir: formdaki tüm kelimelere uygulanabilecek bir makine yapmak mümkün müdür? N(T)0 X , Nerede T keyfi makine, X – rastgele bir kelime ve eğer makine T kelimeye uygulanabilir X A" q 0 |B" , ve eğer araba T kelimeye uygulanamaz X , nihai konfigürasyona yol açacaktır A" q 0 0 B" . Burada bir", B" Ve bir", B"- keyfi kelimeler.

Teorem Başlangıç ​​sözcüğüne uygulanabilirlik sorunu algoritmik olarak karar verilemez, yani bu sorunu yukarıdaki anlamda çözen bir Turing makinesi yoktur.

Yukarıda belirtildiği gibi kendi kendine uygulanabilirlik sorunu için ilk ön adım numaralandırmadır. Bu nedenle, aşağıda bu konu sürekli olarak algoritmalar ve onun üç ana algoritmik model türü için dikkate alınmakta ve çözülmektedir.

Algoritmaların numaralandırılması

Algoritmaların numaralandırılması araştırma ve analizlerinde önemli bir rol oynar. Herhangi bir algoritma sonlu bir sözcük olarak belirlenebildiğinden (bazı alfabelerin sonlu sembol dizisi olarak temsil edilir) ve sonlu bir alfabedeki tüm sonlu sözcüklerin kümesi sayılabilir olduğundan, tüm algoritmaların kümesi de sayılabilir. Bu, doğal sayılar kümesi ile algoritma kümesi arasında bire bir eşlemenin varlığı, yani her algoritmaya bir sayı atama yeteneği anlamına gelir.

Algoritmaların numaralandırılması aynı zamanda algoritmik olarak hesaplanabilen tüm fonksiyonların numaralandırılmasıdır ve herhangi bir fonksiyon sonsuz sayıda sayıya sahip olabilir.

Numaralandırmanın varlığı, algoritmalarla sayılarla aynı şekilde çalışmanıza olanak tanır. Numaralandırma özellikle diğer algoritmalarla çalışan algoritmaların incelenmesinde faydalıdır.

Bir dizi başlangıç ​​nesnesi X ve bir dizi istenen nesne Y ile belirli bir kütle problemi olsun. Kütle probleminin bir çözümünün var olması için, X ve Y kümelerinin elemanlarının yapıcı nesneler olması gerekir. Sonuç olarak bu kümelerin elemanları doğal sayılarla numaralandırılabilir. x∈ X bir başlangıç ​​nesnesi olsun, onun sayısını n(x) ile gösterelim. Orijinal x nesnesi için bir kütle probleminde, n(y) sayısıyla istenen y∈ Y nesnesinin elde edilmesi gerekiyorsa, o zaman f(n(x))=n olacak şekilde bir f: Nn →N aritmetik fonksiyonu tanımlarız. (y).

Kütlesel problemler için aritmetik fonksiyonların oluşturulmasına bir örnek olarak, kütle problemlerini ele alalım.

1. Eğer doğal sayılardan oluşan bir ] dizisi verilmişse, bu diziye 2x1, 3x2,... p(n)xn doğal sayısı atanabilir; burada p(n), n'inci asal sayıdır. Uzunluğu 5 olan bir dizi örneğini ele alalım:

] 2x13x25x37x411x5.

Bu numaralandırma f aritmetik fonksiyonunu tanımlar (örneğin, f(73500) = f(22315372110) = 20315272113 = 4891425).

2. Her rasyonel sayının bir doğal sayısı vardır. Sorunun gerekli nesneleri kümesinin numaralandırılması önemsizdir:

(“evet”, “hayır”) a (1, 0). Belirli bir kütle problemi için, önceki örnekteki tekniği kullanarak bir argümanın aritmetik fonksiyonunu oluşturabilirsiniz veya üç argümandan oluşan bir fonksiyonu (orijinal üçlünün üç sayısı) düşünebilirsiniz.

3. Program metinlerinin numaralandırılması şu şekilde gerçekleştirilebilir: herhangi bir program, 256-ary sayı sisteminde bir sayı kaydediyormuş gibi algılanabilir (programı kaydetmek için ASCII tablo karakterleri kullanılmışsa).

Kütle probleminden aritmetik fonksiyona geçiş, kütle problemine bir çözümün varlığı sorusunu, bir aritmetik fonksiyonun değerlerini argümanından hesaplamanın etkili bir yolunun varlığı sorusuna azaltmamızı sağlar ( argümanlar).

Sayı kümelerinin numaralandırılması

Algoritma teorisinde, birden fazla değişkenin fonksiyonlarının incelenmesinin tek değişkenli fonksiyonların incelenmesine indirgenmesine olanak tanıyan bir teknik yaygınlaşmıştır. Sayı kümelerinin numaralandırılmasına dayanır, böylece sayı kümeleri ile sayıları arasında birebir bir yazışma vardır ve bir sayı kümesinden kendi sayısını ve sayıdan sayı kümesinin kendisini belirleyen işlevler genellikle yinelemelidir. Örneğin, iki bağımsız değişken (x, y) içeren bir fonksiyon için bu h(x, y) eşlemesi şu şekilde olabilir:

Resim 1.

(x, y) çiftlerinin kısmen sıralı bir N(2) kümesi oluşturmasına izin verin. h(x, y) = n verilirse, ters bir eşleme olur: x = h -1 1 (n) ve y= h -1 2 (n), yani h(h -1 1 (n), h -1 2 (n)) = n. Bu, herhangi bir çift (x, y) için n sayısını hesaplamanıza ve bunun tersine, x ve y değerlerini hesaplamak için n sayısını kullanarak hesaplamanıza olanak tanır:

Bu kuralları kullanarak, h 2 (x, y, z) = h(h(x, y), z) = n üçlülerinin numaralandırmasını ve tersine üçlü sayısına göre - değerleri hesaplayabilirsiniz. x, y, z. Örneğin, h 2 (x, y, z) = n ise z= h -1 2 (n), y= h -1 2 (h -1 1 (n))), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n))), h -1 2 (h -1 1 (n)) ), h-12(n)). Üçlüler (x, y, z) kısmen sıralı bir N(3) kümesi oluşturur. Benzer şekilde, keyfi sayıda sayı için elimizde:

h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Eğer h n-1 (x1, x2,…, xn)=m ise, o zaman xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m))), ... ..................................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)) x1 = h -1 2 (h (...h (m)...))

N (1) , N (2) ,..., N (i) ,..., N(n) kümelerinin numaralandırmasına sahip olup, burada N (i), sayı kümeleri (i) kümesidir, M = N (1) N (2) ... N (i) .. N(n) , burada M N. Herhangi bir n N için h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).

Eğer h(x ,1x ,2..., x)n = m ise h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Yukarıdaki formülleri kullanarak x1, x2,…, xn değerlerini geri yükleyebilirsiniz.

İlgili bilgi.

Turing makinesinin tanımı, işleyişi ve belirtilme yöntemleri

Turing makinesi, aşağıdaki parçalardan oluşan belirli bir varsayımsal (soyut) makine olarak anlaşılmaktadır (Şekil 3.1.)

1) her iki yönde de sonsuz olan, hücrelere bölünmüş, her birine alfabeden yalnızca bir karakterin yanı sıra boş l karakterinin yazılabildiği bir bant;

2) herhangi bir zamanda setteki durumlardan birinde olabilen bir kontrol cihazı (çalışma kafası). Her durumda, kafa hücrenin karşısına yerleştirilir ve ona alfabeden bir harf okuyabilir (inceleyebilir) veya yazabilir. A.

Pirinç. 3.1. Turing makinesi

MT'nin işleyişi bir dizi temel adımdan (döngü) oluşur. Her adımda aşağıdaki eylemler gerçekleştirilir:

1. çalışma kafası sembolü okur (inceler);

2. Durumuna ve izlenen sembole bağlı olarak, kafa bir sembol üretir ve onu izlenen hücreye yazar (muhtemelen =);

3. kafa bir hücreyi sağa doğru hareket ettirir (R), sol (Sol) ya da öylece kalır (E);

4. Kafa başka bir içsel duruma geçer. (muhtemelen =).

Durum başlangıç ​​ve son olarak adlandırılır. Son duruma girildiğinde makine durur.

MT'nin tam durumuna denir konfigürasyon . Bu, kasetin hücreleri arasındaki harflerin dağılımı, çalışan kafanın durumu ve izlenen hücredir. Dokunsal konfigürasyon Tşeklinde yazılır: , izlenen hücrenin solundaki alt kelime nerede, izlenen hücredeki harf nerede, sağdaki alt kelime nerededir.

İlk konfigürasyon ve son konfigürasyona standart denir.

MT'nin çalışmasını açıklamanın 3 yolu vardır:

Formun komut sistemi

Fonksiyonel tablo;

Geçişlerin grafiği (diyagramı).

Örneklerle bunlara bakalım.

Örnek 1. Alfabedeki iki kelimenin birleşimini uygulayan bir MT oluşturun. Kasetteki kelimeler * ile ayrılmıştır. Başlangıç ​​konfigürasyonu standarttır.

MT komut sistemi şöyle görünür:

Bu durumda, kafa boş sembole kadar sağa doğru hareket eder.

En sağdaki karakter silinir.

İlk kelime boşsa yıldız işareti silinir.

Sağdaki sözcük karakter karakter sola bir konum kaydırılır.

Standart son konfigürasyona geçiş.

Fonksiyon tablosu

	A	B	*	ben
				-
				-
				-
			-

Tablodaki kısa çizgiler, l sembolünün durumlarda bulunamayacağı anlamına gelir.

a/aL b/bL

Geçiş diyagramı şöyle görünür:

	a/aR b/bR */*R

Standart son konfigürasyon.

MT üzerinde bir sözlük fonksiyonunun hesaplanmasını şu şekilde anlayacağız. İlk konfigürasyonda a kelimesinin bant üzerine yazılmasına izin verin. Değer belirlenirse, makinenin, kelimenin kasete yazıldığı son konfigürasyona sınırlı sayıda adım (döngü) gitmesi gerekir. Aksi takdirde MT süresiz olarak çalışmalıdır.

MT'yi kullanarak sayılar üzerindeki aritmetik işlemlerin performansını tanımlayabilirsiniz. Bu durumda, kasette sayılar, bazı sayı sistemindeki sayılardan oluşan bir alfabedeki sözcükler olarak sunulur ve bu alfabede yer almayan özel bir işaretle, örneğin * ile ayrılır. En sık kullanılan sistem tekli sistemdir ve tek bir sembol –1’den oluşur. Banttaki X sayısı alfabedeki kelimeyle birlikte (veya kısaltılmış haliyle) yazılmıştır. bir=(1).

Bir sayısal fonksiyon, eğer konfigürasyonu konfigürasyona eşleyen bir MT mevcutsa, düzgün bir şekilde hesaplanabilir (veya basitçe Turing hesaplanabilir) ise = sen veya tanımlanmadığında süresiz olarak çalışır.

Örnek 2. Tekli kodda iki sayıyı toplama işlemi.

Başlangıç ​​konfigürasyonu:

Son konfigürasyon: ör. ekleme aslında bir sayı atamaktan ibarettir B numaraya A. Bunu yapmak için ilk 1 silinir ve * yerine 1 konur.

MT'nin tanımını fonksiyonel bir tablo şeklinde veriyoruz:

		*	ben
			-
			-
		-

MT'yi tanımlamaya yönelik yukarıdaki yöntemler pratikte yalnızca basit algoritmalar için kullanılabilir, çünkü karmaşık olanlar için açıklama çok hantal hale gelir. Benzer şekilde, özyinelemeli işlevlerin yalnızca en basit işlevleri ve süperpozisyon, ilkel özyineleme ve minimizasyon operatörlerini kullanarak tanımlanması son derece zahmetli olacaktır. Bu nedenle, bir fonksiyonun ilkel veya kısmi özyinelemeliliği, ilkel veya kısmi özyinelemeliliği zaten kanıtlanmış olan diğer işlevler kullanılarak kanıtlanır.

Benzer şekilde, karmaşık algoritmalara yönelik Turing makineleri mevcut MT'ler kullanılarak oluşturulabilir. Bu yapıya MT bileşimi denir.

MT kompozisyonunun 4 ana yöntemini tanımlayalım:

Sıralı kompozisyon (süperpozisyon);

Paralel kompozisyon;

Dallanma

Sıralı kompozisyon makineler ve bilgi işlem sözlüğü işlevleri ve alfabede A, araba denir T, işlevi hesaplayan. Sıralı kompozisyon şu şekilde tasvir edilmiştir:

ve belirlenir.

Sıralı kompozisyon genellikle algoritmaların doğrusal bölümlerini tanımlamak için kullanılır.

Bir makine inşa etme olasılığı hakkındaki teoremin kanıtı T iki rastgele makinenin sıralı bir bileşimi olan ve son durumun başlangıç ​​durumuyla tanımlanmasıyla gerçekleştirilir.

Örnek 3. A kelimesini a*a kelimesine çeviren bir fotokopi makinesi ve bir toplama makinesi kullanarak tekli kodda 2*X çarpma algoritması oluşturun. Gerekli MT şuna benzer:

Paralel kompozisyon makineler ve bilgi işlem sözlüğü işlevleri ve alfabeleri A Ve İÇİNDE buna göre makine çağrılır T, bir sözlük işlevini değerlendirir. Burada işaret, paralel MD kompozisyonunda kelimeleri ayırmak için kullanılır.

ve şu şekilde belirlenmiştir: .

Aslında, iki MT'nin paralel bileşimi, farklı alfabelerde 2 kelimeden oluşan bir kelimeyi girdi olarak alır ve 2 kelimeden oluşan bir kelimeyi çıktı olarak alır, yani. eş zamanlı ve bağımsız çalışan iki makineyi temsil eder.

Paralel bir kompozisyon uygulamak için iki katlı bantlı bir makine kullanılır. Buna duyulan ihtiyaç, hesaplamanın ve zamanın ardışık olarak gerçekleşmesinden kaynaklanmaktadır ve örneğin ilk önce hesaplandığında, a'dan daha fazla alan gerektirebilir ve b kelimesini bozabilir. İki katlı bant makinesi şu şekilde çalışıyor: b kelimesi ikinci kata yazılıyor ve birinci katta siliniyor, birinci katta hesaplanıyor, ikinci katta hesaplanıyor ve ardından muhtemelen kaydırmayla birinci kata yeniden yazılıyor. .

Paralel kompozisyonu uygulamak N kullanılan makineler N- zemin bandı.

İki katlı bantlı MT komutu şu şekilde yazılır: sırasıyla birinci ve ikinci katlarda yazılan harfler nerede.

Örnek 4. İkili sayı sisteminde makinelerin ve hesaplama fonksiyonlarının paralel bir bileşimini uygulayın ve a+b tekli sistemde.

Giriş sözcüğü şu biçimdedir: .

MT'nin çalışmasını bir komut sistemi ile anlatalım:

Sağa b kelimesine git

B kelimesini ikinci kata yeniden yazma

A kelimesine gitmek için sola gidin

X sayısına 1 ekleniyor.

Sağa b kelimesine ilerleyin.

Sayıların eşzamanlı eklenmesiyle 1. kata sayım b A Ve B.T buna göre. Komut sistemine süslü parantez içindeki komutlar eklendi

Tüm MT'nin son durumu.

Her durumda, algoritmanın başlangıcında, kaynak verilerinin özel değerler (çoğunlukla 0) için bir kontrolünün eklenmesi gerektiğine dikkat edilmelidir; bu gereksinime uyulmaması bir döngüye yol açabilir.

MT bileşimi karmaşık algoritmalar oluşturmak için kullanılabilir. Şu soru ortaya çıkıyor: Herhangi bir algoritma bir MT kompozisyonu olarak uygulanabilir mi? Bu sorunun cevabı şu şekilde verilmektedir: Turing'in tezi , Church'ün tezinin bir benzeri: Her algoritma Turing makineleri kullanılarak uygulanabilir ve bunun tersi de geçerlidir, bir Turing makinesi tarafından uygulanan her süreç bir algoritmadır.

Turing'in tezi bir teorem değildir; kanıtlanması imkansızdır çünkü gayri resmi kavramı içerir " algoritma" Bununla birlikte, uzun yıllara dayanan matematik uygulamaları bu tezin güvenilir bir şekilde doğrulanmasıdır: 50 yıldır, sezgisel anlamda Turing makineleri kullanılarak uygulanamayan hiçbir algoritma bulunamadı.

Çalışmanın amacı: Turing makinelerinin bileşimini kullanarak algoritma yazma konusunda pratik beceriler kazanır.

Teorik bilgiler

MT'yi tanımlamaya yönelik yukarıdaki yöntemler pratikte yalnızca basit algoritmalar için kullanılabilir, aksi takdirde açıklama çok hantal hale gelir. Karmaşık algoritmalar için Turing makineleri, halihazırda mevcut temel MT'ler kullanılarak oluşturulabilir ve bu yapıya denir. kompozisyon MT.

MT kompozisyonunun 4 ana yöntemini tanımlayalım:

Sıralı kompozisyon (süperpozisyon);

Paralel kompozisyon;

Dallanma

1. Turing makinelerinin sıralı bileşimi

Sıralı kompozisyon veya süperpozisyon Turing makineleri ve

Ve
alfabede A, buna araba denir M, fonksiyonun hesaplanması
.

Sıralı kompozisyon şu şekilde tasvir edilmiştir:

ve belirlenmiş
veya
.

2. Turing makinelerinin paralel bileşimi

Paralel kompozisyon arabalar
Ve
, sözlük işlevlerinin hesaplanması
Ve
alfabelerde A Ve İÇİNDE, buna göre makine çağrılır M, bir sözlük işlevini değerlendirir. İşte işaret Paralel MD kompozisyonunda kelimeleri ayırmak için kullanılır.

Paralel bileşim MT
Ve
şu şekilde tasvir edilmiştir:

ve belirlenmiştir:
.

Aslında, iki MT'nin paralel bileşimi, farklı alfabelerdeki 2 kelimeden oluşan bir kelimeyi girdi olarak alır ve yine 2 kelimeden oluşan bir kelimeyi çıktı olarak verir, yani. eş zamanlı ve bağımsız çalışan iki makineyi temsil eder. Paralel bir kompozisyon uygulamak için iki katlı bantlı bir makine kullanılır.

Çift katlı bant makinesi şu şekilde çalışır:

1) kelime kasetin ikinci katına yeniden yazıldı ve birincisinde silindi,

2) hesaplanmış
Birinci katta,

3) hesaplanmış
İkinci katta

4)
muhtemelen bir vardiya ile birinci kata yeniden yazıldı.

Çift katlı bantla MT komutu şu şekilde yazılır:

,

Nerede
– sırasıyla birinci ve ikinci katlara yazılan harfler. Kelimelerin uzunluklarını gösterelim
, sırasıyla,
.

Turing makinesinin çalışmasını iki katlı bantla gösterelim. Genel olarak kelime uzunlukları
Ve
birbirleriyle çakışmazlar ancak görüntünün basitliği açısından eşit olduklarını varsayıyoruz. Daha sonra 1)-4) noktalarının iki katlı bantlı bir MT'ye uygulanması şu şekilde gerçekleştirilir:

Paralel kompozisyonu uygulamak N Turing makineleri kullanılıyor N– zemin bandı.

3. Turing makinelerinin bileşimlerinde dallanma veya koşullu geçiş

Turing makineleri verilirse
Ve
, sözlük işlevlerinin hesaplanması
Ve
ve araba
, bazı yüklemleri değerlendiren P( ) restorasyonla (yani kelimeyi silmeden)  ), daha sonra dallanmayı uygulamak için bir Turing makinesi oluşturulabilir
, fonksiyonun hesaplanması:

Turing makinelerinin bileşim diyagramlarında dallara ayrılması şu şekilde gösterilmektedir:

ve belirlenmiş
, Burada
- makinenin çalışmasının sonucu
, yüklem ise "1" değerlerini alır P( )= ”doğru” ve yüklem ise "0" P( )= “YANLIŞ” ,
– giriş sözcüğünün kopyalanmasını uygulayan bir Turing makinesi
.

4 . Turing makinelerinin bileşimindeki döngü

Döngü kompozisyonda MT, dallanma ile aynı prensiplere göre uygulanır.

" Hoşçakal P( )= ”doğru” , yerine getirmek
»,

Nerede  – ilk infazdan önce kasetteki kelime
ve bir sonraki infazdan sonra .

Döngüyü tasvir etmek için bazı gösterimler sunacağız:

– bir yüklemin hesaplanmasını uygulayan bir Turing makinesi P( ) ;

–MT, giriş sözcüğünün kopyalanmasını uygular
;

–MT, bir döngüde yürütülür ve uygulanır
;

–MT, döngüden çıkarken ve uygularken yürütülür
.

O halde Turing makinelerinin döngüsel bileşimi veya döngüsü şu şekilde gösterilebilir:

Turing Makinesi Kompozisyonlarıyla Programlama:

1) blokları temel MT'lere karşılık gelecek kadar ayrıntılı karmaşık algoritmaların blok diyagramlarının oluşturulması;

2) basit blokları uygulayan temel MT'lerin inşası;

3) temel MT'leri bir MT bileşiminde birleştirmek.

Örnek. Uygulayan bir MT kompozisyonu oluşturun
.

–Giriş sözcüğünün kopyalanmasını gerçekleştiren Turing makinesi;

–MT, sabit sıfırı ayarlama işlevini uygular;

–MT, restorasyonlu hesaplama yüklemi
;

– Seçim fonksiyonunu uygulayan MT -o argüman argümanlar;

–MT, argüman azaltma fonksiyonunun uygulanması tekli kodda 1'e kadar (en soldaki karakteri siler);

– MT, tekli kodda iki sayının toplanmasını gerçekleştirir.

Her durumda, algoritma yürütmenin başlangıcında giriş verilerinin doğruluğunu kontrol etmenin gerekli olduğuna dikkat edilmelidir (örneğin, bölme sırasında argümanın 0'a eşitliği).

Şekil 1.6

Şekil 1.6'da aşağıdaki gösterimler kullanılmıştır:

T 1, T 2 - Turing makineleri;

ST 1, ST 2 - sırasıyla T 1 ve T 2 makinelerinin komut sistemleri;

x - T 1 makinesi için başlangıç ​​bilgisi;

T 1 (x) - T 1 makinesinin çalışmasının sonucu;

T 2 (T 1 (x)) - T 2 makinesinin çalışmasının sonucu.

Örnek olarak, birincisi bir kopyalama işlemi gerçekleştiren, ikincisi ise tekli kodda sayı ekleme işlemini gerçekleştiren iki makinenin bileşimini düşünün. Makinelerin kombinasyonunun bir diyagramı ve elde edilen sonuçlarla birlikte bir bant örneği Şekil 1.7'de gösterilmektedir.

Şekil 1.7

Şekil 1.7'de gösterilen kompozisyon, halihazırda bilinen kopyalama ve ekleme makinelerini kullanarak bir sayıyı ikiye katlama işlemini gerçekleştirmenize olanak sağlar. Böylece, bir dizi spesifik işlemi (örneğin aritmetik işlemler) çözmek için Turing makinelerine yönelik algoritmalar oluşturularak, Turing makinelerinin bileşimleri daha karmaşık sorunları çözmek için oluşturulabilir. Bu durumda, genel bir algoritmanın geliştirilmesi, Turing makinesinde yürütme algoritmalarının zaten bilindiği işlemlerden derlenmesine iner. Bu yaklaşım programlamada prosedür ve fonksiyonların kullanımına benzer.

Bununla birlikte, makine bileşiminin kullanılması, genel algoritmanın oluşturulduğu temel işlemleri gerçekleştirmek için kullanılan algoritmaların bilindiğini varsayar. Bu nedenle, keyfi problemleri çözerken bu yaklaşım, yeni algoritmalar oluşturma ve buna bağlı olarak farklı kontrol ünitelerine sahip Turing makineleri geliştirme ihtiyacını ortadan kaldırmaz. Evrensel bir Turing makinesi kullanarak kontrol ünitesinin yapısını değiştirmeden herhangi bir algoritmayı uygulamak mümkündür.

1.2.2.Evrensel Turing makinesi

Bir Turing makinesi verilmişse (yani giriş, çıkış sinyalleri ve durumlarının alfabeleri, kafanın başlangıç ​​konumu ve makinenin başlangıç ​​durumu biliniyorsa, ayrıca makinenin çalışma tablosu ve başlangıç ​​bilgilerini içeren bir bant da biliniyorsa) ), daha sonra tüm bilgi dönüşümleri, bu makinenin amaçlandığı şekilde adım adım manuel olarak gerçekleştirilebilir. Aslında bu durumda bir Turing makinesinin simülasyonu gerçekleştirilir.

Bir Turing makinesini modellerken gerçekleştirilen işlemleri analiz ederken, modellemenin her adımda aşağıdaki eylemlerin tekrarlanmasından ibaret olduğu tespit edilebilir:

ÄKafanın bulunduğu bant hücresinden bir karakter okunuyor.

ÄMakine çalışma tablosunda bir komut arayın. Arama, makinenin mevcut durumuna ve okunan sembolün değerine göre gerçekleştirilir.

ÄKasete yazılması gereken komuttan sembolün seçilmesi ve kaydedilmesi.

ÄKomuttan kafa hareketi sembolünü seçin ve hareket ettirin.

ÄKomuttan yeni bir makine durumu seçip mevcut durumu yenisiyle değiştirme. Bunu bir sonraki adıma geçerek bu adımların tekrarlanması takip eder.

ST

S.Ü.

Şekil 1.8

Bu temel eylemlerin doğası öyledir ki, hepsi orijinal makinenin çalışmasını simüle edecek başka bir Turing makinesi kullanılarak gerçekleştirilebilir. Modellemenin özü Şekil 1.8'de açıklanmıştır.

Eğer T makinesi bir ST komut sistemine sahipse ve X bilgisine sahip bir bandı işliyorsa, bu durumda çalışması, kendi SU komut sistemine sahip olan başka bir makine U tarafından simüle edilebilir. U makinesinin girişini simüle etmek için yalnızca X bilgilerini içeren bir bant göndermeniz gerekmez. , aynı zamanda komut sistemi (çalışma masası) ST. Bu komut sistemi orijinal bilgilerle aynı kasete kaydedilebilir.

Şekil 1.9

Bir simülasyon makinesinin önemli bir özelliği, SU komut sisteminin (ve buna bağlı olarak kontrol ünitesinin yapısının), simüle edilen T makinesinin çalışma algoritmasına bağlı olmamasıdır. Başka herhangi bir Turing'in çalışmasını simüle edebilen bir Turing makinesi makineye evrensel denir. Evrensel bir Turing makinesinin (UMT) yapısının bir çeşidi Şekil 1.9'da gösterilmektedir.

UMT bandı üç bölgeye ayrılmıştır: bir veri bölgesi, bir mod bölgesi ve bir komut bölgesi.

Veri bölgesi, simüle edilmiş Turing makinesi tarafından işlenmesi gereken ilk bilgileri içerir. Aynı bölgede TBB işleminin sonuçları da kayıt altına alınmaktadır.

Mod bölgesi, belirli bir döngüde veri bölgesi hücresinden okunan mevcut durumu Qt ve mevcut giriş sembolünü Xt kaydeder.

Komut bölgesi simüle edilen makinenin komut sistemini içerir. Komutlar gruplar halinde düzenlenmiştir. İlk grup, Q 0 sembolüyle başlayan komutları, ikinci grup ise Q 1 sembolüyle başlayan komutları içerir. Her grupta komutlar Xt sembolünün değerine göre sıralanır. Böylece bant üzerindeki komutlar simüle edilen makinenin işlem tablosunda olduğu gibi konumlandırılır.

Bilgilerin banttan okunması ve banda yazılması üç kafa kullanılarak gerçekleştirilir: Gd - veri kafası, G r - mod kafası, Gk - komut kafası. Her kafa bandın kendi bölgesi boyunca hareket edebilir.

TBB çalışmaya başlamadan önce bandın her bölgesine ilgili bilgilerin kaydedilmesi gerekmektedir. Başlıklar her bölgede soldaki sembolün üzerine takılmalıdır.

UMT'nin çalışması döngüler halinde gerçekleşir; her döngüde simüle edilen makinenin bir komutunun yürütülmesi simüle edilir. TBB'nin çalışma grafiği Şekil 1.10'da gösterilmektedir.

Şekil 1.10

Şekil 1.10'da aşağıdaki gösterimler kullanılmıştır:

Q G'den P'ye (G'den L'ye, G r P, G r L, G d P, G d L) - kafalardan birini hareket ettirme

Sağ ya da sol;

Q (G k), (G d), (G r) - kafalardan biri tarafından okunan bilgiler;

Q (G k) à (G r) - komut başlığı tarafından verilerin okunması ve bu verilerin yazılması

mod başlığı kullanılarak bant modu bölgesine aktarılır;

Q a, 1 değerini alan yardımcı bir değişkendir, yani

Гк ve Гр kafaları tarafından okunan karakterlerin çakışıp çakışmadığı;

Q in, 1 değerini alan yardımcı bir değişkendir, yani

mevcut (Q t) ve son (Q z) sembollerinin durumları

Q p - komut başlığı aşağıdaki durumlarda 1 değerini alan bir sinyaldir:

sola doğru hareket etmek komuta bölgesinin sınırlarını aştı;

TBB'nin her çalışma döngüsünde aşağıdaki adımlar gerçekleştirilir:

Komuta bölgesini arayın;

bölgede bir ekip arıyorsunuz;

Komut yürütme simülasyonu.

Komut bölgesi arayışı, mod bölgesindeki mevcut Qt durumu ile komut bölgesindeki ilk komutun başlangıcında kaydedilen Qi durumu karşılaştırılarak başlar. Bu durumlar eşit değilse, komut kafası, başın beş adımının sağa doğru gerçekleştirildiği bir sonraki komutun başlangıcına hareket eder (U 0 - U 4 durumları). Qt ve Qi sembolleri eşleşirse, komut başlığı istenilen bölgenin ilk komutunun başındadır. Daha sonra mod bölgesinin Qt ve Xt sembollerine karşılık gelen bir komut için arama başlar. Bunu yapmak için mod başlığı, mod bölgesinin X t sembolünün üzerine, komut başlığı ise mevcut komutta X i sembolünün üzerine yerleştirilir.

Bir bölgede bir komut aramak, bir komut bölgesini aramaya benzer. Bu durumda komut başlığı, X t ve X i karakterleri karşılaştırılana kadar beş adım sağa doğru hareket eder (U 5 - U 9 durumları).

Komutun yürütülmesi (U 10 - U 17 durumları) komut başlığının bir adım sağa hareket ettirilmesiyle başlar, ardından bulunan komuttan okunan Y t sembolü, veri başlığı yerine veri başlığı kullanılarak veri bölgesine yazılır. daha önce Xt sembolünü okuyun. Komut başlığının bir sonraki adımından sonra sağa doğru bulunan komuttan veri kafası taşıma sembolü (Yd) okunur ve veri kafası bu sembole (R,L) uygun olarak hareket ettirilir. Altında, bir sonraki döngüyü hazırlamak için mod başlığını kullanarak mod bölgesine yazılan bir sonraki işlenen sembol (X t +1) bulunur. Daha sonra, komut ve mod başlıkları bir sonraki durum Q t +1 (durumlar) olacak şekilde kurulur.

U 14, U 15). U 16 durumunda çözümün sonlandırılması koşulu kontrol edilir. Bir sonraki durumun sembolü, modellenen makinenin son durumunun sembolü (Q z) ile örtüşmüyorsa, sorunun çözümü tamamlanmaz ve U 17 durumunda komut kafası orijinal konumuna hareket eder ( birinci bölgenin ilk komutunun başlangıcına kadar). Bu durumda TBB bir sonraki döngüyü gerçekleştirmeye hazırdır; Bir sonraki komutun yürütülmesini simüle etmek için.

Q t ve Q z sembolleri çakıştığında problemin çözümü sona erer ve UMT, U z son durumuna geçer.

UMT'nin çalışma sürecini analiz ederken, UMT'nin çalışma algoritmasının simüle edilmiş Turing makinesinin hangi spesifik sorunu çözdüğüne bağlı olmadığı önemli bir sonuca varılabilir. Dolayısıyla farklı makinelerin modellenmesinde UMT kontrol ünitesinin yapısı değişmez. çözülen görevlere bağlı değildir. Bu nedenle UMT, yapısını değiştirmeden herhangi bir algoritmayı çalıştırabileceğiniz gerçekten evrensel bir makinedir.

Bir sonraki UMT komutunun seçilmesi ve çalıştırılması işlemi, bant hücrelerinin sıralı numaralandırılmasıyla ilişkili olduğundan, UMT'deki sorunların çözümü çok fazla zaman gerektirir. Bu nedenle, evrensel de dahil olmak üzere bir Turing makinesi hiçbir zaman inşa edilmedi, ancak içinde modern bilgisayarların bir analogunu görmek zor değil. Bu nedenle, UMT komut bölgesindeki komut sistemi bir makine programına benzer; bir çift Qt ve Xt sembolü makine komutunun adresinin rolünü oynar.

Ancak Turing makinesi algoritmaları tanımlamak için oldukça uygun bir araçtır ve algoritma teorisinde yaygın olarak kullanılır.

Kontrol soruları

ü1.Turing makinelerinin bileşimi nedir?

ü2.Turing makinelerinin bileşimi ne için kullanılır?

ü3.Bir Turing makinesi başka bir makinenin çalışmasını simüle edebilir mi?

Turing mi?

ü4.Bu durumda hangi işlemler yapılıyor?

ü5.Evrensel Turing makinesinin yapısını açıklayınız?

ü6.UMT bandının alanlarında hangi bilgiler kayıtlıdır?

ü7.Turing makinesinin komuta sistemi nedir?

ü8.TBB çalışma döngüsü hangi adımları içerir?

ü9.Komuta bölgesi arama adımının içeriğini açıklayınız.

ü10.“Komut yürütme” adımının içeriğini açıklayınız.

ü11.Bilgiyi kullanarak bilgi işleme süreci hangi özellikleri taşır?

Diyagram bir grafiğe benziyor:

Makine tablası değeri

tablo 1

1. Turing makinelerinde bazı işlemler

Bir Turing makinesinin çalışması tamamen giriş verileri ve komut sistemi tarafından belirlenir. Ancak belirli bir makinenin bir sorunu nasıl çözdüğünü anlamak için kural olarak makine için verilen türden anlamlı açıklamalara ihtiyaç vardır. . Bu açıklamalar genellikle blok diyagramlar ve bazı Turing makinesi işlemleri kullanılarak daha resmi ve kesin hale getirilebilir. Fonksiyonların bileşimini hatırlayın
Ve
çağrılan fonksiyon
kullanıldığında elde edilen hesaplama sonucuna . İçin
bunda karar verildi için gerekli ve yeterlidir üzerinde karar verildi
, A üzerinde karar verildi .

Teorem 1. Eğer
Ve
Turing hesaplanabilir mi, o halde bileşimleri
aynı zamanda Turing de hesaplanabilir.

İzin vermek - hesaplayan bir makine , A - hesaplayan bir makine ve durumlarının kümesi sırasıyla
Ve
.

Bir araba geçiş diyagramı oluşturalım diyagramlardan Ve şu şekilde: başlangıç ​​köşesini belirliyoruz
makine diyagramları terminal köşesi ile
makine diyagramları (komuta sistemleri için bu, komuta sisteminin komuta sistemine atanan ve bunun için
takımlarda ile değiştirin
). İle bir diyagram elde ederiz (
) belirtir. Başlangıç ​​hali duyuracağız
ve son
. Gösterimin basitliği için şunu varsayacağız: Ve Tek değişkenli sayısal fonksiyonlar.

İzin vermek
azimli. Daha sonra
Ve

. Araba aynı konfigürasyon dizisinden geçecektir ancak fark, bunun yerine
içinde gerçekleşecek
. Bu konfigürasyon, makinenin standart başlangıç ​​konfigürasyonudur , Bu yüzden
. Ama bütün takımlar içinde bulunan , O

ve bu nedenle
. Eğer
tanımlanmadıysa o zaman veya durmuyor ve bu nedenle araba durmayacak. Yani araba hesaplar
.

Bu şekilde oluşturulan makine biz buna makinelerin bileşimi diyeceğiz Ve ve atayın
(veya ()) ve ayrıca bir blok diyagramda gösterilmiştir:

1. Turing makinelerinin bileşimi

İzin vermek ,,- aynı harici alfabeye sahip üç Turing makinesi
, iç durumların alfabeleriyle
,
,
ve programlar ,
,
sırasıyla.

Kompozisyon
arabalar Ve isminde arabaT programı kümelerin birleşimi olan
Ve

, Nerede
alınan bir dizi komutu belirtir hepsini değiştir Açık .

1. Turing makinelerinden dallanma

Dallanma makineleri,,İle
, sembolik

isminde arabaT programı şu şekilde elde edilir: from takımlar hariç
Ve
İçin
, sonuçta ortaya çıkan küme çağrılacak ; Daha sonra.

1. Evrensel Turing makinesi

Bir Turing makinesinin komut sistemi, hem belirli bir cihazın çalışmasının açıklaması hem de bir program olarak yorumlanabilir; açıkça bir sonuca yol açan bir dizi talimat. Örnekleri analiz ederken, ikinci yorum istemsizce kabul edilir, yani. herhangi bir Turing makinesinin çalışmasını yeniden üretebilecek bir mekanizma gibi hareket ediyoruz. Herkesin bunu aynı şekilde yapacağına olan güven (eğer hata yapmazlarsa ki bu, Turing makinesi çalışırken de varsayılır), esasen bir Turing'in çalışmasını yeniden üretecek bir algoritmanın varlığına duyulan güvendir. belirli bir programa göre makine, yani. komuta sistemi. Aslında böyle bir algoritmanın sözlü tanımını yapmak zor değil. Ana eylemi döngüsel olarak tekrarlanır ve aşağıdakilerden oluşur: "Mevcut yapılandırma için
Komut sisteminde sol taraftaki komutu bulun
. Bu komutun sağ tarafı şu şekilde ise
, ardından mevcut konfigürasyonda değiştirin
Açık
(yapılandırma ortaya çıkıyor
); sağ tarafta form varsa
, ardından değiştirin
Açık
. Algoritmanın sözlü açıklaması hatalı olabilir ve resmileştirilmesi gerekebilir. Turing makinesi şu anda algoritma kavramının resmileştirilmesi olarak tartışıldığı için, açıklanan yeniden üretim algoritmasını uygulayan bir Turing makinesi oluşturma probleminin ortaya çıkması doğaldır. Tek değişkenli fonksiyonları hesaplayan Turing makineleri için bu problemin formülasyonu şu şekildedir: bir Turing makinesi oluşturun , iki değişkenli bir fonksiyonun hesaplanması ve herhangi bir makine için komuta sistemi ile
, Eğer
tanımlanmış (yani eğer makine ilk verilerde durur ) Ve
eğer durmaz
durmuyor. Bu özelliğe sahip herhangi bir makineyi arayacağız evrensel Turing makinesi. Bu formülasyonu herhangi bir sayıda değişkene genelleştirmek zor değildir.

Üniversal bir makine inşa ederken ortaya çıkan ilk sorun , şu gerçeğinden kaynaklanmaktadır: diğer Turing makineleri gibi sabit bir alfabeye sahip olmalıdır
ve sabit bir durum kümesi
. Bu nedenle komuta sistemi
ve rastgele bir makinenin başlangıç ​​verileri onu öylece makine kayışına aktaramazsınız (her zaman bir araba vardır , alfabeler
Ve
hangisi güç bakımından üstündür
Ve
ya da sadece onunla örtüşmüyor).

Çözüm, karakterlerin
Ve
alfabedeki sembollerle kodlanmıştır
. İzin vermek
,
. Her zaman şunu varsayacağız
Ve
(Bu iki sembol her zaman sayılarla çalışan her makinenin alfabesinde bulunur). Kodları belirtelim Ve başından sonuna kadar
Ve
ve bunları şu şekilde tanımlayın:
; başkası için
; son durum için


, Eğer

. Kod
bu araba için her zaman bir uzunluğu vardır (biçimi)
ve kod
- biçim . Semboller ,
hadi içeri girelim
yani
,
,
. Karakter kodu , bu kelimeyi oluşturan karakterlerin kodlarından oluşan, belirtiyoruz
. Böylece, evrensel bir makine probleminin formülasyonunun son hali herhangi bir araba için ve kelimeler alfabe
.

Evrensel bir Turing makinesinin varlığı, talimat sisteminin
herhangi bir araba iki şekilde yorumlanabilir: ya orijinal cihazın çalışmasının bir açıklaması olarak veya evrensel bir makine için program olarak . Bir kontrol sistemi tasarlayan modern bir mühendis için bu durum doğaldır. Herhangi bir kontrol algoritmasının donanımda (uygun bir devre kurarak) veya yazılımda evrensel bir kontrol bilgisayar programı yazarak uygulanabileceğini çok iyi biliyor.

Bununla birlikte, evrensel bir algoritmik cihaz fikrinin, uygulanmasına yönelik modern teknik araçların (elektronik, katı hal fiziği vb.) geliştirilmesiyle tamamen ilgisiz olduğunu ve teknik değil matematiksel bir gerçek olduğunu anlamak önemlidir. teknik araçlardan bağımsız soyut matematiksel terimlerle tanımlanır ve ayrıca son derece az sayıda çok temel başlangıç ​​​​kavramlarına dayanır. Algoritma teorisi üzerine temel çalışmaların (özellikle Turing'in çalışmalarının) modern bilgisayarların yaratılmasından önce 30'larda ortaya çıkması karakteristiktir.

Bu çifte yorum, iki mühendislik uygulama seçeneğinin ana avantajlarını ve dezavantajlarını soyut düzeyde korur. Belirli araba çok daha hızlı çalışır; ayrıca makinenin kontrol cihazı oldukça hantaldır (yani durum ve komutların sayısı fazladır). Ancak değeri sabittir ve bir kez oluşturulduktan sonra keyfi büyüklükteki algoritmaların uygulanması için uygundur. İhtiyaç duyulan tek şey, doğal olarak kontrol cihazından daha ucuz ve daha basit bir yapıya sahip olduğu düşünülen büyük miktarda banttır. Ayrıca algoritmayı değiştirirken yeni cihazlar oluşturmanıza gerek kalmayacak, sadece yeni bir program yazmanız yeterli olacaktır.