Turing makinesi

Olarak teorik bilgisayar biliminin , bir Turing makinesi operasyon soyut model mekanik işlem cihazları gibi a, bilgisayar . Bu model, 1936'da Alan Turing tarafından algoritma veya "mekanik prosedür" kavramına kesin bir tanım vermek için tasarlandı . Teorik bilgisayar bilimlerinde , özellikle algoritmik karmaşıklık ve hesaplanabilirlik alanlarında hala yaygın olarak kullanılmaktadır .

Başlangıçta, bilgisayardan önce icat edilen Turing'in makinesi kavramının, iyi tanımlanmış bir prosedürü uygulayan, sonsuz bir şeridin kutularının içeriğini değiştiren, bu içeriği sonlu bir semboller kümesinden seçen sanal bir kişiyi temsil etmesi gerekiyordu . Öte yandan, işlemin her aşamasında, kişi kendini sonlu bir dizi durum arasında belirli bir duruma yerleştirmelidir. "Eğer ise: Prosedür gibi temel adımlar bakımından formüle edilmiştir devlete 42 ve Baktığınız hücredeki sembolüdür" 0 1" " daha sonra bu sembolü değiştirmek", gidin devlete 17 , ve şimdi sağdaki bitişik kareye bakın ”.

Kilise tezi algoritmik bir prosedür dayalı herhangi bir problemlerdendir bir Turing makinesi tarafından çözülebileceğini belitleri. Algoritmik prosedürlerin kesin bir tanımını varsaymadığı için bu tez matematiksel bir ifade değildir. Öte yandan, “kabul edilebilir programlama sistemi” kavramını tanımlamak ve bu tür sistemlerin gücünün Turing makinelerininkine eşdeğer olduğunu göstermek mümkündür (bunlar Turing-tamamlıdır ).

Tanım

Adı "makine" olsa da, Turing makinesi soyut bir kavramdır, yani matematiksel bir nesnedir. Bir Turing makinesi aşağıdaki bileşenlere sahiptir:

Bir sonsuz şerit ardışık kareler ayrılmıştır. Her kutu belirli bir sonlu alfabenin bir sembolünü içerir . Alfabe, "boş sembol" (aşağıdaki örneklerde '0') olarak adlandırılan özel bir sembol ve bir veya daha fazla başka sembol içerir. Bandın sol veya sağda sonsuz uzunlukta olduğu varsayılır, başka bir deyişle, makinenin çalışması için her zaman yeterli bant uzunluğuna sahip olması gerekir. Şerit kutularının varsayılan olarak “beyaz sembolü” içerdiğini düşünüyoruz;
Şerit üzerindeki sembolleri okuyup yazabilen ve şeridin soluna veya sağına hareket edebilen bir okuma/yazma kafası ;
Turing makinesinin mevcut durumunu saklayan bir durum kaydı . Olası durumların sayısı her zaman sınırlıdır ve makinenin çalıştırılmadan önceki ilk durumu olan "başlangıç durumu" adı verilen özel bir durum vardır;
Makineye şeride hangi sembolü yazacağını, oynatma çubuğunun nasıl hareket ettirileceğini (örneğin , bir kutu için " " , sağa bir kutu için " ") ve yenisinin ne olduğunu söyleyen bir eylem tablosu . , şeritte okunan sembole ve makinenin mevcut durumuna bağlı olarak. Belirli bir okuma sembolü ve mevcut durum kombinasyonu için herhangi bir eylem yoksa, makine durur. $\ sol ok$ $\ sağ ok$

Resmi tanımlama

Bir Turing makinesinin birbirine yakın birkaç resmi tanımı verilebilir. Nispeten yaygın olan bunlardan biri burada seçilir. Bir Turing makinesi, şu durumlarda bir quintuplettir : ${\ görüntü stili (Q, \ Gama, q_ {0}, \ delta, F)}$

$Q$ sonlu bir dizi durumları ;
$\Gama$ bir çalışma alfabe içeren bant sembolleri, belirli bir sembol (denilen boş ) ; $B$ $B \ in \ Gama$
$q_0$ bir ilk durumu , ; $Q'da q_ {0} \$
$\ delta: Q \ kez \ Gama \ - Q \ kez \ Gama \ kez \ {\ leftarrow, \ rightarrow \}$ bir geçiş fonksiyonu ;
$F$ kabul eden durumlar (veya son, terminaller) kümesidir . $F \ alt küme Q$

Tam ve deterministik bir Turing makinesinin bir modelidir; ie tanımlanmış ve benzersizdir. ${\ displaystyle \ forall q \ Q'da, \ forall \ gamma \ in \ Gamma, \ delta (q, \ gamma)}$

tanımındaki oklar , okuma/yazma kafasının iki olası hareketini, yani sola hareketi ve sağa hareketi temsil eder. Bu geçiş fonksiyonunun anlamı şu örnekte açıklanabilir: Turing makinesi durumdaysa ve sembolünü okuyorsa , yerine yazıyorsa , duruma gidiyor ve oynatma kafasını sola hareket ettiriyor demektir. $\delta$ $\ delta (q_ {1}, x) = (q_ {2}, y, \ sol ok)$ $q_ {1}$ $x$ $y$ $x$ $q_ {2}$

Turing makinesinin çalışması şu şekildedir: hesaplamasının her aşamasında, makine bulunduğu duruma ve okuma kafasının bulunduğu şerit kutusunda yazılı sembole göre gelişir. Bu iki bilgi parçası, geçiş işlevini kullanarak makinenin durumunu güncellemek için kullanılır. İlk anda, makine durumundadır ve bandın ilk sembolü programın girişidir. Makine bir terminal durumuna girdiğinde durur. Hesaplamanın sonucu, makine tarafından art arda okunan sembollerin oluşturduğu kelimedir. $q_0$

Tanımdaki olası girişlerin bir alfabesini sınırlayabiliriz . Bu nedenle , makinenin hesaplama adımları için tüm alfabenin belirli sembollerini ayırarak bu alfabe üzerinde daha hassas çalışmak mümkündür . Özellikle, beyaz sembol girişin bir parçası olmamalıdır ve bu nedenle ikincisinin sonunu tanımlayabilir . $\ Sigma$ $\Gama$ $B$

Aşağıdaki ilk örnek, bir makinenin terminal durumundaysa durduğu ve şeritte belirli bir karakteri (burada beyaz sembol) okuduğu bir Turing makinesinin çok az farklı bir sürümünü kullanır. Aşağıdaki ikinci örnek, Turing'in 1936 tarihli makalesinde verdiği ilk tarihsel örnektir: Durmayan bir makinedir.

Örnekler

'1' sayısını ikiye katlayın

Aşağıdaki Turing makinesinin alfabesi {'0', '1'}, '0' "beyaz sembol"dür. Şeridin bir dizi '1' içerdiğini ve okuma/yazma kafasının başlangıçta en soldaki '1' üzerinde olduğunu varsayın. Bu makine, iki seri arasına bir '0' koyarak '1' sayısını ikiye katlama etkisine sahiptir. Örneğin, "111", "1110111" olur.
Makinenin olası durumları kümesi {e1, e2, e3, e4, e5} ve başlangıç durumu e1'dir.
Eylem tablosu aşağıdaki gibidir:

Geçiş tablosu örneği

eski durum	Sembolü oku	yazılı sembol	Hareket	Yeni durum
e1	0	(Durmak)
e1	1	0	Doğru	e2
e2	1	1	Doğru	e2
e2	0	0	Doğru	e3
e3	1	1	Doğru	e3
e3	0	1	Ayrıldı	e 4
e 4	1	1	Ayrıldı	e 4
e 4	0	0	Ayrıldı	e5
e5	1	1	Ayrıldı	e5
e5	0	1	Doğru	e1

Bu makineyi iki '1'lik bir seri için çalıştırmak şu şekilde olacaktır (okuma/yazma kafasının bant üzerindeki konumu koyu ve kırmızı harflerle yazılmıştır):

Yürütme (1)

Sahne	Durum	Kurdele
1	e1	1 1
2	e2	0 1
3	e2	01 0
4	e3	010 0

Yürütme (2)

Sahne	Durum	Kurdele
5	e 4	01 0 1
6	e5	0 1 01
7	e5	0 101
8	e1	1 1 01

Yürütme (3)

Sahne	Durum	Kurdele
9	e2	10 0 1
10	e3	100 1
11	e3	1001 0
12	e 4	100 1 1

Yürütme (4)

Sahne	Durum	Kurdele
13	e 4	10 0 11
14	e5	1 0 011
15	e1	11 0 11
	(Durmak)

Bu makinenin davranışı bir döngü olarak tanımlanabilir:

Yürütmeye e1 durumunda başlar, ilk 1'i 0 ile değiştirir.
Ardından, 0 (veya boşluk) ile karşılaşana kadar 1'leri (bu örnekte yalnızca bir tane) atlayarak sağa hareket etmek için e2 durumunu kullanır ve e3 durumuna geçer.
Daha sonra e3 durumu, sonraki 1 dizisini (başlangıçta hiçbiri) atlamak ve karşılaşılan ilk 0'ı 1 ile değiştirmek için kullanılır.
Durum e4, bir 0 bulunana kadar sola dönmeyi ve e5 durumuna geçmeyi mümkün kılar.
Durum e5 daha sonra başlangıçta e1 durumu tarafından yazılan bir 0 bulunana kadar tekrar sola hareket etmeyi mümkün kılar.
Makine daha sonra bu 0'ı 1 ile değiştirir, bir hücre sağa hareket eder ve yeni bir döngü yinelemesi için tekrar e1 durumuna geçer.

Bu işlem, e1 0'a düşene kadar tekrarlanır (1'in iki dizisi arasındaki ortadaki 0'dır); bu sırada makine durur.

Üçte bir ikili olarak hesaplayın

Aşağıdaki örnekte, Turing makinesinin boş bir şeridi vardır ve 01010101010101 ...

Sonsuz bir tablo örneği

eski durum	yazılı sembol	Hareket	Yeni durum
NS	0	Doğru	B
B	1	Doğru	NS

Bu makinenin çalışması şöyle olacaktır (okuma/yazma kafasının bant üzerindeki konumu koyu ve macenta karakterlerle yazılmıştır ):

Sonsuz Makineyi Çalıştırmak

Sahne	Durum	Kurdele
1	NS	0
2	B	0 1
3	NS	01 0
4	B	010 1
5	NS	0101 0
6	B	01010 1
7	NS	010101 0
8	B	0101010 1
...	...	01010101 ...

Bu makinenin davranışı sonsuz bir döngü olarak tanımlanabilir:

Yürütmeye a durumunda başlar, 0 ekler ve sağa doğru hareket eder.
Sonra b durumuna geçer, 1 ekler ve sağa hareket eder.
a durumuna döner ve ilk adımı tekrarlar.

Bu makine, ikili olarak yazımı 0.010101010101 olan üçüncü bir hesaplamanın karşılığıdır ...

Üniversal Turing Makineleri

Alan Turing'in ufuk açıcı makalesinde gösterdiği gibi, "evrensel Turing makinesi" olarak adlandırılan ve herhangi bir diğer Turing makinesinin davranışını "simülasyon" yapabilen bir Turing makinesi yaratmak mümkündür. "Simülasyon", evrensel Turing makinesinin girdi olarak bir makine T ve veri D'nin bir kodlamasını alması durumunda , veri D' nin girdi olarak verileceği makine T ile aynı sonucu ürettiği anlamına gelir .

Evrensel bir Turing makinesi, hesaplanabilir her şeyi hesaplama kapasitesine sahiptir: daha sonra bunun Turing-tamamlanmış olduğunu söyleriz . Uygun kodlamayı sağlayarak, herhangi bir özyinelemeli işlevi simüle edebilir , herhangi bir özyinelemeli dili analiz edebilir ve herhangi bir kısmen karar verilebilir dili kabul edebilir . Göre Church-Turing tezi , evrensel Turing makinesi tarafından çözülebilir problemler çözülebilir sorunlar tam olarak algoritması ile veya bir hesaplama beton yöntemi .

Turing makinesinin gerçekleştirilmesi

Turing makinesi bir düşünce nesnesidir: şeridi sonsuzdur ve bu nedenle Turing makinesinin belleği sonsuzdur. Bir Turing makinesi , belleği sınırlı olan bir bilgisayarın aksine hiçbir zaman bellek taşması oluşturmaz . Bu bellek problemini unutarak, modern bir bilgisayarda bir Turing makinesini simüle edebiliriz .

Tamamen mekanik Turing makineleri yapmak da mümkündür. Bir düşünce nesnesi olan Turing makinesi, bu nedenle , bazen oldukça orijinal olan teknikler kullanılarak sayısız vesileyle şeyleştirildi , burada birkaç örneği var:

İçinde nisan 2011, Jim MacArthur, şerit üzerindeki bilgi taşıyıcısı olarak bilyeli yataklara sahip kompakt bir mekanik 5 sembol Turing makinesi yaptı.
İçinde Mart 2012, Turing yılı (tr) vesilesiyle , École normale supérieure de Lyon'dan bir grup öğrenci, elektronik olmadan tamamen Lego parçalarından yapılmış bir Turing makinesi üretti .

İçinde Aralık 2013, Turing makinelerini gerçeğe dönüştürmek için deneysel bir prototip, (elektro-mekanik: Turing döneminden kalma teknolojilerle yapılmış), dairesel bir şeritle ve nispeten kolay programlanabilir. Taşınabilir iki parça olarak tasarlanmış olup sunum ve dersler için kullanılabilir.
Ekim 2020'de Thierry Delattre (Dunkirk) tarafından tasarlanan, maksimum 12 durumlu ve 3 sembollü bir alfabe ile algoritmalar için programlanabilen eğitici bir Turing makinesi. 50 algoritma hafızada saklanabilir. 22 eyaletli ve 8 sembollü bir versiyon Şubat 2021'den kalmadır.

Referanslar ve bibliyografya

Referanslar

(içinde) Harry R. Lewis ve Christos Papadimitriou , Hesaplama Teorisinin Unsurları . Prentice-Hall , 1982; ikinci baskı Eylül 1997.
"SON" , CNRTL: "Aslında, aralarında orada yüzüyor finale ve finale : 1 st plur gibi görünüyor. langırt. mahkeme. ve yazarlar, dilbilimcilerin ve ekonomistlerin ikincisi ” .
Kévin Perrot, “ Hesaplanabilirlik. Kurs 1: Turing makineleri ” , univ-mrs.fr'de ,bahar 2019( Kasım 2020'de danışıldı )
(içinde) Jim MacArthur, " Turing Machine " , srimech.blogspot.fr'de ,8 Haziran 2012( 20 Şubat 2018'de erişildi ) .
" RUBENS Projesi " üzerinde, rubens.ens-lyon.fr ,Mart 2012( 20 Şubat 2018'de erişildi ) .
David Larousserie, Le Monde , " Havası olmayan tamamen mekanik bir makine " , limonde.fr'de ,22 Haziran 2012( 20 Şubat 2018'de erişildi ) .
Marc Raynaud, “ A Programmable Prototype to Realize the Turing Machine ” , machinedeturing.org'da ( 19 Şubat 2018'de erişildi ) .
Ouest-France , " Marc Raynaud, bilgili bir matematikçi mucit " , ouest-france.fr'de ,14 Şubat 2018( 14 Eylül 2020'de erişildi ) .
" Turing Makinesi - Kod, daha sonra ilgi çekici hafif animasyonlar, ikili sayılar, sayı dizileri veya boş zamanlarınızda icat edebileceğiniz başka herhangi bir uygulama üzerinde matematiksel hesaplamalara sahip olur!" » (Erişim tarihi: 19 Mart 2021 )

bibliyografya

Kılavuzlar

Olivier Carton, Resmi diller, hesaplanabilirlik ve karmaşıklık: matematik veya bilgisayar bilimlerinde lisans ve yüksek lisans derecesi, matematiğin toplanmasının bilgisayar bilimi seçeneği , Paris, Vuibert ,2008, 237 s. ( ISBN 978-2-7117-2077-4 , SUDOC 128299258 ) ;
Jean-Michel Autebert, Hesaplanabilirlik ve Karar Verilebilirlik , Paris, Masson,1992, 118 s. ( ISBN 978-2-225-82632-0 , SUDOC 002676494 ) ;
Éric Jacopin, Les Machines de Turing: Bir problemin karmaşıklığının karakterizasyonuna giriş , Toulouse, Éditions Cépaduès ,2009, 264 s. ( ISBN 978-2-85428-865-0 , SUDOC 132323214 ) ;

Turing

Alan Turing ve Jean-Yves Girard , La machine de Turing , Paris, Éditions du Seuil,1995, 192 s. [ baskı ayrıntısı ] ( ISBN 9782020369282 ) ; bu çalışma özellikle orijinal makalenin Fransızca çevirisini (Julien Basch ve Patrice Blanchard tarafından) ve Emil Post tarafından orada görünen hataların düzeltmesini içerir;
(tr) Alan Turing, “ Entscheidungsproblem için bir Uygulama ile Hesaplanabilir Sayılar Üzerine ”, Londra Matematik Derneği Bildirileri, Seri 2 , cilt. 45,1936, s. 230-265 ( çevrimiçi okuyun ) ;
(fr) Alan Turing, 'Hesaplanabilir Sayılar'ın Özeti ( çevrimiçi okuyun ). - Paris Bilimler Akademisi'nin Tasvirleri İçin Bir Not taslağı.

Kleene

Stephen Cole Kleene , Metamatematiğe Giriş , Amsterdam, Kuzey Hollanda,1952, x + 550 s. ( SUDOC 005505526 , çevrimiçi sunum ) - Sudoc bildirimine göre 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009'da özellikle Wolters-Noordhoff (Groningen) ( ISBN 0720421039 ) tarafından çok sayıda yeniden basım . Birçok çeviri.
(tr) , (fr) Stephen Cole Kleene, Mathematical Logic , Dover ,1967- Dover'ın yeniden basımı, 2001, ( ISBN 0-486-42533-9 ) . Jean Largeault tarafından Fransızca çeviri , Logique mathématique , Armand Colin, 1971 ve Gabay 1987 ( ISBN 2-87647-005-5 ) .

: Bu makale için kaynak olarak kullanılan belge.

Şuna da bakın:

İlgili Makaleler

Deterministik olmayan Turing makinesi ;
Olasılık Turing makinesi ;
Alternatif Turing makinesi ;
Simetrik Turing makinesi ;
Blum-Shub-Smale makinesi: üzerinde hesaplama yapan makineler için bir genelleme ; $\ matematik bb {R}$
Karar sorunu ;
Düşünce deneyi ;
Oracle (Turing makinesi) ;
Taklit Oyunu , Alan Turing'in Benedict Cumberbatch ilehayatını anlatan film ;
Oluşturulabilir işlev .

Dış bağlantılar

Christophe Gombert ve Hugo Deboise imzalı "The Turing Machine Realized" filmi ücretsiz olarak online izlenebilir.
Alan Turing'in kesintiye uğrayan dehası : Bernard Chazelle tarafından planlanan bir BnF konferansının sunumu ve bibliyografyası19 Mart 2014
Hamdi Ben Abdallah, “ Turing makinesi nasıl çalışır? », Aralıklar ,22 Mart 2013( çevrimiçi okuyun ), bir Turing makinesini denemeye izin veren makale.