{"id":24537,"date":"2014-11-01T13:12:33","date_gmt":"2014-11-01T11:12:33","guid":{"rendered":"https:\/\/bilimvegelecek.com.tr\/?p=24537"},"modified":"2018-05-04T16:14:29","modified_gmt":"2018-05-04T13:14:29","slug":"turingden-gunumuze-turing-makineleri","status":"publish","type":"post","link":"https:\/\/bilimvegelecek.com.tr\/index.php\/2014\/11\/01\/turingden-gunumuze-turing-makineleri","title":{"rendered":"Turing\u2019den g\u00fcn\u00fcm\u00fcze Turing makineleri"},"content":{"rendered":"

Turing makinesi ve evrensellik fikri, ortaya konulu\u015fundan y\u0131llar sonra, g\u00fcn\u00fcm\u00fcz bilgisayarlar\u0131nda kullan\u0131lan mimarinin temelini olu\u015fturmakla kalmad\u0131. Giderek, hesaplaman\u0131n do\u011fan\u0131n temel s\u00fcre\u00e7lerinden biri oldu\u011fu, evreni b\u00fcy\u00fck bir bilgisayar olarak d\u00fc\u015f\u00fcnmemiz gerekti\u011fi s\u00f6ylenir oldu. Bunlar\u0131 Alan Turing\u2019in \u00e7ocukken annesinin masas\u0131nda g\u00f6r\u00fcp hayran oldu\u011fu daktilodan esinlenerek 24 ya\u015f\u0131nda kurgulad\u0131\u011f\u0131 bir modele bor\u00e7luyuz.<\/em><\/p>\n

Alan Turing d\u00fcnyay\u0131 de\u011fi\u015ftiren bir dahiydi. \u0130nsanl\u0131\u011fa katk\u0131s\u0131n\u0131 \u00f6zetlemek bile bu yaz\u0131 i\u00e7in hedefledi\u011fimden uzun s\u00fcrer. B\u00fcy\u00fck bulu\u015flar\u0131ndan sadece birini ortaya \u00e7\u0131k\u0131\u015f\u0131ndan bug\u00fcne kadarki geli\u015fimiyle anlatmaya \u00e7al\u0131\u015faca\u011f\u0131m.<\/p>\n

Karar Problemi<\/strong><\/p>\n

17. y\u00fczy\u0131l\u0131n b\u00fcy\u00fck bilginlerinden Gottfried Leibniz, d\u00f6rt aritmetik i\u015flemi de do\u011frudan yapabilen ilk makineyi ger\u00e7ekle\u015ftirmek i\u00e7in y\u0131llar\u0131n\u0131 vermi\u015fti. \u201cEn basit fikirli ki\u015finin bile makine kullanarak kesinlikle yapabilece\u011fi hesaplar i\u00e7in m\u00fckemmel insanlar\u0131n saatlerce k\u00f6leler gibi u\u011fra\u015fmas\u0131na de\u011fmez!\u201d diyen Leibniz, hedefini sadece d\u00f6rt i\u015flemle s\u0131n\u0131rl\u0131 tutmuyordu. Verilen bir matematiksel \u00f6nermenin do\u011fru mu yanl\u0131\u015f m\u0131 oldu\u011funu belirleyecek bir makinenin de yap\u0131labilece\u011fini d\u00fc\u015f\u00fcnd\u00fc ve bunun i\u00e7in ilk ad\u0131m olarak \u00f6nermelerin ifade edilebilece\u011fi net bir dil tasarlamaya giri\u015fti.<\/p>\n

As\u0131rlar ge\u00e7ti. 1928\u2019de David Hilbert ve Wilhelm Ackermann, Leibniz\u2019in hayaline benzer bir proje i\u00e7in zaman\u0131n geldi\u011fini d\u00fc\u015f\u00fcnd\u00fcler. Matematik d\u00fcnyas\u0131na, art\u0131k yeterince geli\u015ftirilmi\u015f olan bi\u00e7imsel dille yaz\u0131lm\u0131\u015f herhangi bir mant\u0131ksal \u00f6nermenin verilen \u00f6nc\u00fcller kullan\u0131larak kan\u0131tlanabilir olup olmad\u0131\u011f\u0131n\u0131 saptayabilen bir y\u00f6ntemin (\u015fimdi kulland\u0131\u011f\u0131m\u0131z terimle, bir \u201calgoritma\u201dn\u0131n) bulunmas\u0131 i\u00e7in \u00e7a\u011fr\u0131da bulundular. B\u00f6yle bir algoritman\u0131n var oldu\u011fundan hi\u00e7 ku\u015fkular\u0131 yoktu, sadece birisinin onu ke\u015ffetmesi gerekiyordu, sonras\u0131nda art\u0131k matematik\u00e7iler ispat i\u015flerini bu algoritmaya g\u00f6re \u00e7al\u0131\u015fan makinelere b\u0131rakabilir, ilgilendikleri herhangi bir \u00f6nermenin do\u011fru mu yanl\u0131\u015f m\u0131 oldu\u011funu otomatik olarak \u00f6\u011frenebilirlerdi! Hilbert\u2019in radyo kayd\u0131 da olan \u00fcnl\u00fc \u201cBilmeliyiz. Bilece\u011fiz!\u201d s\u00f6z\u00fc bu kesin g\u00fcveni yans\u0131t\u0131r.<\/p>\n

\"\"
Alan Turing (1912-1954).<\/figcaption><\/figure>\n

Y\u0131llar Hilbert\u2019i haks\u0131z \u00e7\u0131kard\u0131. Gen\u00e7 \u0130ngiliz matematik\u00e7i Alan Turing bu \u201cKarar Problemi<\/strong>\u201d \u00fczerinde \u00e7al\u0131\u015ft\u0131 ve 1936\u2019da \u015fa\u015f\u0131rt\u0131c\u0131 bir \u00e7\u00f6z\u00fcme ula\u015ft\u0131: B\u00f6yle bir algoritma yoktu! Dolay\u0131s\u0131yla, her derde deva bir \u201cmant\u0131k makinesi\u201d yapmak da m\u00fcmk\u00fcn de\u011fildi. Ama Turing bu \u00f6nemli bulu\u015fun tad\u0131n\u0131 \u00e7\u0131karabildi mi dersiniz?<\/p>\n

Okyanusun di\u011fer yan\u0131nda, Princeton\u2019da matematik\u00e7i Alonzo Church de ayn\u0131 konuda y\u0131llarca \u00e7al\u0131\u015fm\u0131\u015f ve Turing\u2019inkinden farkl\u0131 bir y\u00f6ntemle ayn\u0131 sonuca ula\u015farak birka\u00e7 ay \u00f6nce yay\u0131mlam\u0131\u015ft\u0131. Bu nedenle Church\u2019den habersiz \u00e7al\u0131\u015fan Turing\u2019in makalesini g\u00f6nderdi\u011fi dergi \u00f6zg\u00fcn olmad\u0131\u011f\u0131 gerek\u00e7esiyle yay\u0131mlamaya yana\u015fm\u0131yordu. Sorunu iki makaleyi de okuyan Cambridge hocas\u0131 Max Newman \u00e7\u00f6zd\u00fc. Newman, Turing\u2019in ispat\u0131nda kulland\u0131\u011f\u0131 y\u00f6ntemin kendi ba\u015f\u0131na \u00f6nemli bir katk\u0131 oldu\u011funu fark etti ve yay\u0131nc\u0131lar\u0131 ikna etmeyi ba\u015fard\u0131. B\u00f6ylece bilgisayar biliminin kurucu metni yay\u0131mlanabilmi\u015f oldu.<\/p>\n

\u201cMakine\u201d<\/strong><\/p>\n

Peki Church\u2019\u00fcn \u00e7al\u0131\u015fmas\u0131nda olmay\u0131p Turing\u2019inkinde olan, bu nedenle i\u015fin uzmanlar\u0131na, s\u00f6zgelimi efsanevi Kurt G\u00f6del\u2019e \u201cHah, i\u015fte \u00a0Karar Problemi \u015fimdi \u00e7\u00f6z\u00fclm\u00fc\u015f oldu\u201d dedirten bu ikna edici y\u00f6ntem neydi? Bunu anlamak i\u00e7in \u00a0Karar Problemini tan\u0131t\u0131rken de\u011findi\u011fimiz bir noktay\u0131 tekrar vurgulamak gerekli: Problem bir algoritman\u0131n ortaya konulmas\u0131n\u0131 istiyordu, ama o zamanlar \u201calgoritma\u201d dedi\u011fimiz \u015feyin net matematiksel bir tan\u0131m\u0131 yoktu. Ak\u0131llara \u201cbir hesaplamay\u0131 ger\u00e7ekle\u015ftirmek i\u00e7in kullan\u0131labilen, mu\u011flak olmayan, basit ad\u0131mlardan olu\u015fan bir yordam\u201d gibi bir tarif geliyordu, ama bir \u015feyin b\u00f6yle bir y\u00f6ntem olup olmad\u0131\u011f\u0131n\u0131 kesinkes ay\u0131rt etmeye yarayan bir tan\u0131m mevcut de\u011fildi. G\u00f6del, Church\u2019\u00fcn \u00e7al\u0131\u015fmas\u0131nda esas ald\u0131\u011f\u0131 olduk\u00e7a soyut \u00e7er\u00e7evenin bu anlamda her \u201cyap\u0131labilir hesap i\u015fi\u201dni ger\u00e7ekle\u015ftirebilece\u011fine ikna olmam\u0131\u015ft\u0131 \u00f6rne\u011fin.<\/p>\n

Turing ise makalesine matematiksel i\u015flemler yapan (ve yorulma, uyuma, ac\u0131kma, ya\u015flanma, dikkat da\u011f\u0131n\u0131kl\u0131\u011f\u0131, k\u00e2\u011f\u0131t\/kalem eksikli\u011fi vs. pratik sorunlar\u0131 hi\u00e7 ya\u015famayan) bir insan\u0131 temsil eden bir \u201cmakine\u201d t\u00fcr\u00fcn\u00fc gerekli netlikte tan\u0131mlayarak ba\u015fl\u0131yordu. Bu ba\u011flant\u0131y\u0131, a\u015fa\u011f\u0131da g\u00f6rece\u011finiz gibi, o kadar basit \u015fekilde anlat\u0131yordu ki, okuru insanlar\u0131n yapabilece\u011fi her cins hesap i\u015finin bu t\u00fcrden bir makinece de ger\u00e7ekle\u015ftirilebilece\u011fine ikna ediyor, b\u00f6ylece nihayet \u201calgoritma\u201d kavram\u0131na bir tan\u0131m getirmi\u015f oluyordu. Bu noktadan sonra ispat\u0131n geri kalan\u0131, do\u011fru mu yanl\u0131\u015f m\u0131 oldu\u011funu bu t\u00fcrden makinelerin hi\u00e7birinin saptayamayaca\u011f\u0131 bir mant\u0131ksal \u00f6nermenin sunulmas\u0131ndan, dolay\u0131s\u0131yla Hilbert\u2019in istedi\u011fi \u201cher derde deva\u201d algoritman\u0131n var olmad\u0131\u011f\u0131n\u0131n g\u00f6sterilmesinden ibaretti.<\/p>\n

Daha sonra Church\u2019\u00fcn takt\u0131\u011f\u0131 adla, bir \u201cTuring makinesi\u201d (TM) \u015fu iki bile\u015fenden olu\u015fur:<\/p>\n

– Kareli bir defterin ilk sat\u0131r\u0131n\u0131 (ya da e\u011fer isterseniz bir tuvalet k\u00e2\u011f\u0131d\u0131n\u0131) sonsuza dek uzatarak g\u00f6z\u00fcn\u00fczde canland\u0131rabilece\u011finiz, her karesine bir sembol yaz\u0131labilen, ve istenen karesine eri\u015filip oradaki sembol\u00fcn okunmas\u0131na ve istenirse silinip yerine bir ba\u015fkas\u0131n\u0131n yaz\u0131lmas\u0131na imk\u00e2n veren bir teyp. (Modelledi\u011fimiz insan\u0131n s\u0131n\u0131rs\u0131z miktarda k\u00e2\u011f\u0131t\/kalem\/silgi kullanabilmesi bu \u015fekilde temsil ediliyor. Bu insan\u0131n belli bir anda k\u00e2\u011f\u0131d\u0131n sadece bir noktas\u0131na bakabilece\u011fi ger\u00e7e\u011fine de, bu okuma\/yazma i\u015flemlerinin sadece teyp \u00fczerinde sa\u011fa sola gezdirilebilen tek bir \u201cteyp kafas\u0131\u201dn\u0131n o anda \u00fcst\u00fcnde oldu\u011fu karede yap\u0131labilmesiyle sad\u0131k kal\u0131n\u0131yor.)<\/p>\n

– (Modelledi\u011fimiz insan\u0131n belle\u011fi gibi) s\u0131n\u0131rl\u0131 bir miktarda bilgi tutabilen bir kontrol birimi. Uygulanacak yordam\u0131n ad\u0131mlar\u0131 da bu bilgilere dahildir. G\u00fcn\u00fcm\u00fcz\u00fcn terminolojisini kullan\u0131rsak, bu \u201cprogram\u201d makinenin bir sonraki ad\u0131m\u0131nda ne yapmas\u0131 gerekti\u011fini belirler. Her program sonlu say\u0131da (\u201c\u015fimdi \u00fcst\u00fcnde oldu\u011fun karede Y harfini g\u00f6r\u00fcyorsan onu silip yerine Z harfini yaz, sonra kafay\u0131 bir soldaki kareye getir\u201d, \u201c8 numaral\u0131 komuta atlay\u0131p oradan devam et\u201d, \u201c\u00e7al\u0131\u015fmay\u0131 durdur\u201d vb.) basit \u201ckomut\u201dlardan olu\u015fur.Her komut birim zamanda icra edilebilir.<\/p>\n

\"\"
Bir Turing makinesi modeli.<\/figcaption><\/figure>\n

Belli bir i\u015flev i\u00e7in haz\u0131rlanm\u0131\u015f bir TM\u2019nin yan\u0131tlamas\u0131n\u0131 istedi\u011fimiz soruyu teybine yan yana gerekli say\u0131da kareye birer sembol kondurarak yazabiliriz. Bu noktadan sonra makine \u00e7al\u0131\u015ft\u0131r\u0131l\u0131r ve her ad\u0131mda program\u0131nda s\u0131radaki komutu ger\u00e7ekle\u015ftirir. Program\u0131n makineye \u201cgirdi\u201d olarak verilen sorunun yan\u0131t\u0131n\u0131, gerekli i\u015flemlerle hesaplat\u0131p teybe yazd\u0131rmas\u0131, sonra da \u00e7al\u0131\u015fmay\u0131 durdurmas\u0131 beklenir. (Kimi programlar kimi girdilerle ba\u015flat\u0131ld\u0131klar\u0131nda sonsuz bir d\u00f6ng\u00fcye girip hi\u00e7 durmayabilirler, \u00f6rne\u011fin s\u00fcrekli \u201cteyp kafas\u0131n\u0131 bir sa\u011fdaki kareye getir\u201d komutunu tekrarlayan bir makine sonsuza dek \u00e7al\u0131\u015facakt\u0131r. Her girdi i\u00e7in sonlu say\u0131da ad\u0131m sonucunda bir yan\u0131t verip duran yordamlar\u0131 tercih ederiz elbet.)<\/p>\n

Hepsi bu! Turing ne kadar kar\u0131\u015f\u0131k ve uzun olursa olsun her belirli hesap yordam\u0131n\u0131n yukar\u0131da anlat\u0131lan komutlar\u0131n basitli\u011finde par\u00e7alara b\u00f6l\u00fcnebilece\u011fini,bu yordam\u0131 uygulayan bir insan\u0131n yapt\u0131klar\u0131n\u0131n da bu cinsten bir makine taraf\u0131ndan taklit edilebilece\u011fini iddia ediyordu. D\u00fc\u015f\u00fcn\u00fcn, s\u00f6z\u00fc edilen t\u00fcrden bir i\u015fi yaparken (\u00f6rne\u011fin iki b\u00fcy\u00fck say\u0131y\u0131 \u00e7arparken) kafan\u0131za ilkokuldayken yerle\u015ftirdi\u011finiz bir program\u0131n ad\u0131mlar\u0131n\u0131 s\u0131rayla icra eder, k\u00e2\u011f\u0131tta yaz\u0131l\u0131 say\u0131lara bak\u0131p beyninizdeki \u00e7arp\u0131m tablosundan bu kurallara g\u00f6re getirdi\u011finiz yeni bir \u015feyler yazar, en sondaki toplamay\u0131 da benzer \u015fekilde halleder, sonunda da kendinizi aranan yan\u0131t\u0131 yazm\u0131\u015f bulursunuz, de\u011fil mi?<\/p>\n

Church ve Turing k\u0131sa s\u00fcrede birbirlerinin y\u00f6ntemlerinin e\u015f g\u00fc\u00e7te oldu\u011funu, yani Church\u2019\u00fcn modeline uyan her hesap y\u00f6ntemi i\u00e7in ayn\u0131 i\u015fi yapabilen bir TM kurulabilece\u011fini g\u00f6sterdiler. Y\u0131llar boyunca \u201calgoritma\u201d kavram\u0131 i\u00e7in \u00f6nerilen \u00e7ok say\u0131da di\u011fer farkl\u0131 g\u00f6r\u00fcn\u00fc\u015fl\u00fc model de incelendikten sonra, bunlar\u0131n her birini taklit edebildi\u011fi g\u00f6r\u00fclen TM modelinin kavram\u0131n \u201cresmi\u201d tan\u0131m\u0131 olarak kabul edilmesi konusunda bir ku\u015fku kalmad\u0131.<\/p>\n

Evrensellik<\/strong><\/p>\n

Buraya kadar\u0131 bile b\u00fcy\u00fck ba\u015far\u0131yd\u0131, ama Turing\u2019in makalesinin \u00e7a\u011f de\u011fi\u015ftiren bulgusundan daha s\u00f6z etmedik. Akl\u0131n\u0131za gelen her algoritma i\u00e7in ayr\u0131 bir TM in\u015fa edilebilir, \u00f6rne\u011fin yukar\u0131da s\u00f6z\u00fcn\u00fc etti\u011fimiz ilkokul tipi \u00e7arpma yordam\u0131n\u0131 ger\u00e7ekle\u015ftiren, girdi olarak verilen iki say\u0131n\u0131n \u00e7arp\u0131m\u0131n\u0131 hesaplayan bir TM tasarlayabilirsiniz. Ama Turing o g\u00fcn i\u00e7in \u00e7ok \u015fa\u015f\u0131rt\u0131c\u0131 olan bir uygulama g\u00f6sterdi: Ba\u015fka TM\u2019leri taklit etme i\u015fi!<\/p>\n

Turing \u201cevrensel\u201d bir TM tasarlam\u0131\u015ft\u0131. Bu makineye E diyelim. E\u2019ye girdi olarak can\u0131n\u0131z\u0131n istedi\u011fi (diyelim ki ad\u0131 T olan) bir ba\u015fka TM\u2019nin tarifini ve yan\u0131na da T\u2019ye girdi olarak verilecek soruyu verebilirsiniz. Bu durumda E, T\u2019nin o soru \u00fczerindeki \u00e7al\u0131\u015fmas\u0131n\u0131 ba\u015ftan sona birebir taklit eder ve e\u011fer T bu \u00e7al\u0131\u015fman\u0131n sonunda duracaksa da, T ne yan\u0131t veriyorsa ayn\u0131s\u0131n\u0131 verir. Turing TM\u2019lerin ba\u015fka her sistemin benzetimini (sim\u00fclasyon) yapabilme \u00f6zelli\u011fini, tek bir fiziksel makineye sonsuz say\u0131da de\u011fi\u015fik i\u015f yapt\u0131rabilmek i\u00e7in kullanabilece\u011fimizi ke\u015ffetmi\u015fti.<\/p>\n

\"\"
Matematik\u00e7i Alonzo Church (1903-1995) de ayn\u0131 konuda y\u0131llarca \u00e7al\u0131\u015fm\u0131\u015f ve Turing\u2019inkinden farkl\u0131 bir y\u00f6ntemle ayn\u0131 sonuca ula\u015fm\u0131\u015ft\u0131.<\/figcaption><\/figure>\n

O g\u00fcne dek insanlar her makineyi sadece tek bir i\u015f i\u00e7in tasarlarlard\u0131. Otomobiller ula\u015f\u0131m, buzdolaplar\u0131 so\u011futma, radyolar da ileti\u015fim i\u00e7indi. Oysa Turing bize tek bir makine al\u0131p ona bir\u00e7ok farkl\u0131 makineyi taklit ettirebilece\u011fimizi s\u00f6yl\u00fcyordu.<\/p>\n

Bilgisayarlardan s\u00f6z etti\u011fimizi anlad\u0131n\u0131z, de\u011fil mi? \u00c7a\u011f\u0131m\u0131zda bu \u201chesaplama evrenselli\u011fi\u201d kavram\u0131n\u0131 anlamak kolay, \u00e7\u00fcnk\u00fc tek bir cihaz sat\u0131n al\u0131p onun \u00fczerinde muhasebe program\u0131, oyun program\u0131, kelime i\u015fleme program\u0131, resim yapma program\u0131 vs. bin t\u00fcrl\u00fc farkl\u0131 program \u00e7al\u0131\u015ft\u0131rarak bin de\u011fi\u015fik makinenin keyfini \u00e7\u0131kartmak bize do\u011fal geliyor. Ama Turing makalesini yazd\u0131\u011f\u0131nda t\u00fcm bu farkl\u0131 i\u015fleri yapabilen tek bir makine bilimkurgudan ibaretti. Ak\u0131ll\u0131 telefonlar\u0131m\u0131z\u0131 bize o hediye etti.<\/p>\n

Do\u011fa yasalar\u0131<\/strong><\/p>\n

Albert Einstein akl\u0131n\u0131 kullanarak evrende bir h\u0131z s\u0131n\u0131r\u0131 oldu\u011funu ke\u015ffetmi\u015fti; ne kadar g\u00fc\u00e7 harcarsan\u0131z harcay\u0131n, asla \u0131\u015f\u0131k h\u0131z\u0131na eri\u015femezsiniz. Turing \u00a0Karar Problemini tuzla buz ederken benzer bir do\u011fa yasas\u0131n\u0131n da bilgisayarlar\u0131 (ve asl\u0131na bakarsan\u0131z TM\u2019lerin taklit edebilece\u011fi her \u015feyi, yani insanlar\u0131 da) ba\u011flad\u0131\u011f\u0131n\u0131 ve ne kadar u\u011fra\u015f\u0131rsak u\u011fra\u015fal\u0131m asla \u00e7\u00f6zemeyece\u011fimiz kimi problemlerin var oldu\u011funu kan\u0131tlam\u0131\u015f oldu. Bu fikri g\u00f6zden ge\u00e7irelim:<\/p>\n

Benzetim yetenekleri sayesinde TM\u2019ler g\u00fcn\u00fcm\u00fcz\u00fcn (ve gelece\u011fin) bilgisayarlar\u0131n\u0131 taklit edebilir, herhangi bir bilgisayar ne yaparsa bir TM de onun\u201cgibi yapabilir\u201d. Bu nedenle TM bilgisayar biliminin temel modelidir: \u0130\u015flemci h\u0131z\u0131, ekran\u0131n ka\u00e7 renk g\u00f6sterdi\u011fi, fare mi klavye mi kullan\u0131ld\u0131\u011f\u0131 vb. g\u00fcncel teknolojik ayr\u0131nt\u0131lar\u0131 g\u00f6z ard\u0131 edip \u015fimdi ve gelecekte her bilgi i\u015flem ayg\u0131t\u0131nda olmas\u0131 gereken ortak unsurlar\u0131 (girdi, bellek, sonlu kaynaklar kullanan ad\u0131mlardan olu\u015fan belirli bir program ve \u00e7\u0131kt\u0131) temsil etti\u011fi i\u00e7in, e\u011fer belli bir i\u015fi hi\u00e7bir TM\u2019nin yapamayaca\u011f\u0131n\u0131 kan\u0131tlarsak o i\u015fin hi\u00e7bir bilgisayarca yap\u0131lamayaca\u011f\u0131n\u0131 da kan\u0131tlam\u0131\u015f oluruz. Ve Turing de bunu ba\u015fard\u0131.<\/p>\n

\u015eu problemi d\u00fc\u015f\u00fcn\u00fcn: Ben size bir bilgisayar program\u0131n\u0131n metnini verece\u011fim. Siz de bu program\u0131 inceleyip sonlu bir zaman i\u00e7inde bana bu program\u0131n \u00e7al\u0131\u015ft\u0131r\u0131lmas\u0131 halinde sonsuz bir d\u00f6ng\u00fcye girip girmeyece\u011fini s\u00f6yleyeceksiniz. Bu i\u015fi size verebilece\u011fim her girdi (yani her farkl\u0131 program) i\u00e7in do\u011fru yan\u0131t\u0131 vererek bitirmenizi sa\u011flayacak bir algoritma var m\u0131d\u0131r? Dikkat edin, \u201cVerilen program\u0131 \u00e7al\u0131\u015ft\u0131r\u0131p bakar\u0131m, cevab\u0131 ona g\u00f6re veririm\u201d diyemezsiniz, \u00e7\u00fcnk\u00fc bunu yaparsan\u0131z ve program\u0131n \u00e7al\u0131\u015fmas\u0131 uzun s\u00fcre beklemenize kar\u015f\u0131 bitmezse onun sonsuz bir d\u00f6ng\u00fcye mi girdi\u011fini, yoksa sadece uzun s\u00fcre \u00e7al\u0131\u015fm\u0131\u015f ve art\u0131k durmas\u0131na az kalm\u0131\u015f bir program m\u0131 oldu\u011funu bilemezsiniz. Karara benzetim yoluyla de\u011fil, \u201cinceleme\u201d yoluyla varman\u0131z gerekmekte.<\/p>\n

(Laf aram\u0131zda, b\u00f6yle bir algoritma bulsan\u0131z \u00e7ok iyi olurdu, \u00e7\u00fcnk\u00fc yaz\u0131l\u0131m geli\u015ftiren insanlar bu kontrol\u00fc yapabilmeyi ger\u00e7ekten \u00e7ok isterler. Yani bu i\u015fi yapan bir program\u0131 \u00e7ok iyi fiyata satabilirdiniz. Ama maalesef…)<\/p>\n

Turing \u00a0Karar Problemiyle ilgili kan\u0131t\u0131n\u0131n i\u00e7inde g\u00f6z kama\u015ft\u0131r\u0131c\u0131 basitlikte bir y\u00f6ntemle i\u015fte bu \u201cDurma Problemi\u201dnin de hi\u00e7bir TM (ve dolay\u0131s\u0131yla hi\u00e7bir bilgisayar program\u0131, hi\u00e7bir insan, vs.) taraf\u0131ndan yukar\u0131da istenen genellikte \u00e7\u00f6z\u00fclemeyece\u011fini g\u00f6sterdi. Evrende hi\u00e7bir uygarl\u0131k ne denli u\u011fra\u015f\u0131rsa u\u011fra\u015fs\u0131n, bu i\u015fi yapan bir program yazamaz. Bu t\u00fcrden sorular\u0131 bu \u00f6l\u00e7\u00fctlere g\u00f6re yan\u0131tlayan hi\u00e7bir makine hi\u00e7bir zaman in\u015fa edilemez. Sizi bilmem ama, bana bu \u00e7ok net bir do\u011fa yasas\u0131 gibi geliyor. Sonraki y\u0131llarda bu \u201ckararla\u015ft\u0131r\u0131lamazl\u0131k\u201d \u00f6zelli\u011fine sahip bir\u00e7ok problem daha ke\u015ffedildi.<\/p>\n

Karma\u015f\u0131kl\u0131k<\/strong><\/p>\n

Turing \u015fifre \u00e7\u00f6zme alan\u0131ndaki \u00e7al\u0131\u015fmalar\u0131yla ba\u015f\u0131n\u0131 2. D\u00fcnya Sava\u015f\u0131 gibi bir beladan kurtard\u0131\u011f\u0131 kendi devletinin hoyratl\u0131\u011f\u0131 sonucu gen\u00e7 ya\u015fta \u00f6ld\u00fc. O sa\u00e7ma sapan muameleye maruz kalmasayd\u0131, daha neler yarat\u0131rd\u0131 kim bilir. Ama TM\u2019lerin hik\u00e2yesi bitmedi.<\/p>\n

\"\"
Ba\u015fka bir Turing makinesi modeli.<\/figcaption><\/figure>\n

\u00c7\u00f6z\u00fcm y\u00f6ntemini bildi\u011finiz iki problem d\u00fc\u015f\u00fcn\u00fcn, \u00f6rne\u011fin ikisini de ilkokulda \u00f6\u011frendi\u011finiz toplama ve \u00e7arpmay\u0131. 12345 ve 67890 say\u0131lar\u0131n\u0131 birbiriyle toplamak m\u0131 daha \u00e7ok vaktinizi al\u0131r, yoksa \u00e7arpmak m\u0131? Daha uzun, s\u00f6zgelimi onar rakaml\u0131 iki say\u0131 verseydim peki?<\/p>\n

Algoritmalar birbirleriyle bu fikir esas al\u0131narak kar\u015f\u0131la\u015ft\u0131r\u0131labilir. Her algoritma i\u00e7in yatay eksenin verilen girdinin uzunlu\u011funu, dikey eksenin de bu algoritman\u0131n bu uzunluktaki olas\u0131 girdilerden en zoru i\u00e7in ka\u00e7 ad\u0131m \u00e7al\u0131\u015faca\u011f\u0131n\u0131 g\u00f6sterdi\u011fi bir \u201cad\u0131m say\u0131s\u0131 grafi\u011fi\u201d \u00e7izdi\u011fimizi d\u00fc\u015f\u00fcnelim. Ku\u015fkusuz girdilerin uzunlu\u011fu artt\u0131k\u00e7a ad\u0131m say\u0131lar\u0131 da artacakt\u0131r, ama bu art\u0131\u015f\u0131 g\u00f6steren grafi\u011fin \u015fekli problemden probleme farkl\u0131 olacakt\u0131r. S\u00f6zgelimi toplama algoritmam\u0131z i\u00e7in bu i\u015f yap\u0131ld\u0131\u011f\u0131nda ad\u0131m say\u0131s\u0131n\u0131n kabaca do\u011frusal olarak artt\u0131\u011f\u0131n\u0131, yani grafi\u011fi sonsuza do\u011fru uzatt\u0131\u011f\u0131m\u0131zda \u015feklinin soldan sa\u011fa y\u00fckselen bir do\u011fruya benzeyece\u011fini g\u00f6rece\u011fiz.<\/p>\n

\u0130lkokulda \u00f6\u011frendi\u011fimiz \u00e7arpma algoritmas\u0131 i\u00e7in benzer bir grafikse uzat\u0131ld\u0131k\u00e7a do\u011frusal de\u011fil, karesel olarak (t\u00fcrevi giderek artarak) y\u00fckselir. Bir algoritman\u0131n girdisi uzad\u0131k\u00e7a ad\u0131m say\u0131s\u0131 ne kadar h\u0131zl\u0131 y\u00fckseliyorsa, bu o algoritman\u0131n genelde o denli yava\u015f oldu\u011fu anlam\u0131na gelir. \u00d6yle ki toplamay\u0131 yava\u015f, \u00e7arpmay\u0131 ise \u00e7ok daha h\u0131zl\u0131 i\u015flemcileri olan iki farkl\u0131 bilgisayarda yapsan\u0131z ve ikisini ayn\u0131 anda ba\u015flatsan\u0131z bile, yeterince \u00e7ok rakaml\u0131 say\u0131lar i\u00e7in toplama i\u015flemi \u00e7arpmadan daha \u00f6nce bitecektir.<\/p>\n

A problemini \u00e7\u00f6zen en h\u0131zl\u0131 algoritman\u0131n ad\u0131m say\u0131s\u0131 grafi\u011fi yukar\u0131daki anlamda B problemininkinden daha h\u0131zl\u0131 y\u00fckseliyorsa A\u2019n\u0131n B\u2019den daha \u201czor\u201d oldu\u011funu (teknik terimle, \u201czaman karma\u015f\u0131kl\u0131\u011f\u0131n\u0131n daha y\u00fcksek\u201d oldu\u011funu) s\u00f6yleriz. Elbette bu kar\u015f\u0131la\u015ft\u0131rmalar\u0131 adil \u015fekilde yapabilmek i\u00e7in t\u00fcm algoritmalar\u0131 ayn\u0131 dilde yazmam\u0131z gerekir. Do\u011fru tahmin ettiniz, burada yine algoritma kavram\u0131n\u0131n resmi tan\u0131m\u0131 olarak TM\u2019ler devreye girer.<\/p>\n

Halihaz\u0131rda kulland\u0131\u011f\u0131m\u0131z bilgisayarlar, ve az sonra de\u011finece\u011fimiz tek bir istisna d\u0131\u015f\u0131nda, TM tan\u0131m\u0131n\u0131n fiziksel ger\u00e7ekli\u011fe dayanan t\u00fcm g\u00fcncel s\u00fcr\u00fcmleri, yukar\u0131da anlat\u0131lan TM modelince hem zaman, hem de benzer \u015fekilde tan\u0131mlanan bellek miktar\u0131 karma\u015f\u0131kl\u0131\u011f\u0131 a\u00e7\u0131s\u0131ndan verimli \u015fekilde taklit edilebilir. (Yani yeni t\u00fcrden her makinenin yapt\u0131\u011f\u0131 her i\u015fi, genel resmi de\u011fi\u015ftirmeyen ufak bir yava\u015flama ve d\u0131\u015f bellek ihtiyac\u0131nda ufak bir art\u0131\u015f ile bir TM\u2019ye de yapt\u0131rabilirsiniz.) Bu nedenle problemlerin s\u0131n\u0131fland\u0131r\u0131lmas\u0131 i\u00e7in TM\u2019ler aras\u0131nda yap\u0131lan bir zaman karma\u015f\u0131kl\u0131\u011f\u0131 kar\u015f\u0131la\u015ft\u0131rmas\u0131n\u0131n ger\u00e7ek d\u00fcnyadaki cihazlar\u0131m\u0131z i\u00e7in de ge\u00e7erli olaca\u011f\u0131ndan eminiz.<\/p>\n

Kan\u0131tlamay\u0131 ba\u015farabildiklerimiz bir yana, h\u00e2l\u00e2 kesin zorluk derecesini bilemedi\u011fimiz problemlerin \u00e7oklu\u011fu ve ilgin\u00e7li\u011fi, hesaplama karma\u015f\u0131kl\u0131\u011f\u0131 kuram\u0131n\u0131, halen kuramsal bilgisayar biliminin ve hatta t\u00fcm matemati\u011fin en heyecanl\u0131 konular\u0131ndan biri haline getirmi\u015ftir. Kesin olarak s\u00f6yleyebildi\u011fimiz bir sonuca \u00f6rnek olarak iki problem tan\u0131mlayay\u0131m:<\/p>\n

Kom\u015fu kentler aras\u0131ndaki karayolu ba\u011flant\u0131lar\u0131n\u0131n anlat\u0131ld\u0131\u011f\u0131 bir listeye bakarak ad\u0131 verilen iki kentten birinden di\u011ferine karayolundan gitmenin m\u00fcmk\u00fcn olup olmad\u0131\u011f\u0131n\u0131 saptama i\u015fine Yol Bulma Problemi diyelim. (Anadolu gibi her yerden her yere karayoluyla ula\u015f\u0131labilen de\u011fil, muhtemelen kopukluklar\u0131n oldu\u011fu bir co\u011frafya ve kentlerin ad\u0131n\u0131n alfabetik s\u0131rada verildi\u011fi bir liste d\u00fc\u015f\u00fcn\u00fcn.)<\/p>\n

\u0130ki ki\u015finin 3\u2019e 3\u2019l\u00fck kareli bir alana s\u0131rayla X ve O harflerini koyup bir do\u011fru \u00fczerine ayn\u0131 harften 3 tanesini getirmeye \u00e7al\u0131\u015ft\u0131\u011f\u0131 \u00fcnl\u00fc XOX oyununun istenen bir boyuta geni\u015fletilip kurallar\u0131n da buna uyumlu olarak genelle\u015ftirildi\u011fi bir oyun tarif edilmi\u015ftir. Bu oyunun verilen \u201cm\u201d, \u201cn\u201d ve \u201ck\u201d say\u0131lar\u0131 i\u00e7in m\u2019ye n\u2019lik alanda bir do\u011fruya k sembol yerle\u015ftirme hedeflenen s\u00fcr\u00fcm\u00fcnde bir oyuncuya di\u011fer oyuncu ne yaparsa yaps\u0131n oyunu kazand\u0131racak bir stratejinin var olup olmad\u0131\u011f\u0131n\u0131 saptama i\u015fine de XOX Problemi diyelim.<\/p>\n

Evet, Yol Bulma Probleminin XOX Probleminden \u00e7ok ama \u00e7ok daha kolay oldu\u011fu bilimsel olarak kan\u0131tlanm\u0131\u015ft\u0131r! Sa\u011fduyuya uygun g\u00f6r\u00fcnen bu sonucun g\u00fc\u00e7 yan\u0131, bir problem (bu durumda XOX Problemi) i\u00e7in ilk akl\u0131n\u0131za gelen algoritmadan \u00e7ok daha verimli bir ba\u015fka algoritman\u0131n var olmad\u0131\u011f\u0131n\u0131 kan\u0131tlamakta yatar. \u00d6rne\u011fin \u00e7arpma i\u00e7in ilkokulda \u00f6\u011frendi\u011fimizden \u00e7ok daha h\u0131zl\u0131 (ama h\u00e2l\u00e2 toplaman\u0131nkinden yava\u015f) bir algoritman\u0131n 2007 y\u0131l\u0131nda ke\u015ffedildi\u011fini biliyor muydunuz?<\/p>\n

Modelin yeni s\u00fcr\u00fcmleri<\/strong><\/p>\n

Turing\u2019in modeli sa\u011fduyuya uygun olarak tasarland\u0131\u011f\u0131 i\u00e7in kabul edilmesi kolay oldu. Fakat fizik bilimi modelin do\u011fan\u0131n i\u015fleyi\u015fi hakk\u0131nda bar\u0131nd\u0131rd\u0131\u011f\u0131 kimi sa\u011fduyusal varsay\u0131mlar\u0131n do\u011fru olmad\u0131\u011f\u0131n\u0131 s\u00f6yl\u00fcyor. S\u00f6zgelimi, TM modeli belirlenimcidir (deterministik), belli bir TM\u2019ye belli bir girdi sunuldu\u011funda t\u00fcm davran\u0131\u015f\u0131 kesinlikle belirlenmi\u015f olur; ayn\u0131 i\u015flem ka\u00e7 kez yap\u0131l\u0131rsa yap\u0131ls\u0131n t\u0131pat\u0131p ayn\u0131 sonu\u00e7 \u00e7\u0131kar; sapmalara, hatalara yer yoktur. Ger\u00e7ek d\u00fcnya pek b\u00f6yle de\u011fildir! Benzer \u015fekilde, s\u0131n\u0131rs\u0131z miktarda ikincil bellek (\u201chard disk\u201d) kullanma imk\u00e2n\u0131, sonlu miktarda madde i\u00e7eren evrenimizde ger\u00e7ek\u00e7i g\u00f6r\u00fcnmemektedir. Turing\u2019den sonraki y\u0131llarda t\u00fcm bu varsay\u0131mlar sorguland\u0131 ve modelin ger\u00e7e\u011fi daha iyi yans\u0131tan s\u00fcr\u00fcmleri tan\u0131mland\u0131. Bu modellerden ikisini inceleyece\u011fiz.<\/p>\n

Daha \u00f6nce tan\u0131mlad\u0131\u011f\u0131m\u0131z temel TM modeline bir \u201cpara at\u0131\u015f\u0131\u201dn\u0131n sonu\u00e7lar\u0131na g\u00f6re kontrol ak\u0131\u015f\u0131n\u0131 belirleyebilme hakk\u0131 verelim. Bu \u00f6zellik makinenin icra edebilece\u011fi komut t\u00fcrlerine \u201c1\/2 olas\u0131l\u0131kla 5 numaral\u0131 komuta, 1\/2 olas\u0131l\u0131kla da 9 numaral\u0131 komuta atla\u201d gibisinden bir \u201colas\u0131l\u0131ksal dallanma\u201d komutu eklenerek hayata ge\u00e7irilebilir. Bu yeni makine t\u00fcr\u00fcne \u201cOlas\u0131l\u0131ksal TM\u201d (OTM) denir.<\/p>\n

TM\u2019lerin aksine OTM\u2019ler belirlenimci olmad\u0131klar\u0131ndan her soruya her zaman ayn\u0131 yan\u0131t\u0131 vermeyebilirler. Elbette biz her zaman do\u011fru yan\u0131t\u0131 isteriz, ama hata olas\u0131l\u0131\u011f\u0131 daima s\u0131f\u0131r olan bir OTM\u2019nin hi\u00e7bir i\u015fi standart bir TM\u2019den daha h\u0131zl\u0131 yapamayaca\u011f\u0131 kolayca kan\u0131tlanabilir. Az da olsa bir miktar, diyelim trilyonda bir hata olas\u0131l\u0131\u011f\u0131n\u0131 sineye \u00e7ekersek OTM\u2019lerin kimi i\u015fleri (\u00f6rne\u011fin verilen bir say\u0131n\u0131n asal olup olmad\u0131\u011f\u0131n\u0131 saptama i\u015fini) bilinen en iyi TM\u2019den daha h\u0131zl\u0131 yapt\u0131\u011f\u0131n\u0131 g\u00f6sterebiliriz. OTM\u2019ler ger\u00e7ekten TM\u2019lerden \u00fcst\u00fcn m\u00fcd\u00fcr? Hen\u00fcz bilmiyoruz, ama uzmanlar\u0131n \u00e7o\u011funlu\u011fu bir g\u00fcn her problem i\u00e7in az hata yapan bir OTM\u2019ninkine denk h\u0131zda bir TM bulundu\u011funun g\u00f6sterilebilece\u011fine inan\u0131yor.<\/p>\n

Kuantum<\/strong><\/p>\n

Yukar\u0131da TM\u2019lerin bir istisna hari\u00e7 \u00f6nerilen t\u00fcm ciddi alternatif modelleri az bir yava\u015flamayla taklit edebildiklerinden s\u00f6z etmi\u015ftik. \u015eimdi o istisnay\u0131 anlatma zaman\u0131 geldi.<\/p>\n

20. y\u00fczy\u0131l\u0131n ba\u015flar\u0131nda fizikte bir devrim ya\u015fand\u0131. Art\u0131k do\u011fan\u0131n \u00e7ok, ama \u00e7ok tuhaf kurallar\u0131 oldu\u011funu biliyoruz. Temel par\u00e7ac\u0131klar ayn\u0131 anda iki ayr\u0131 yerde, iki farkl\u0131 durumda olabiliyorlar s\u00f6zgelimi. \u0130nanmas\u0131 zor, ama ku\u015fku b\u0131rakmayacak kesinlikte saptanm\u0131\u015f bir do\u011fa yasas\u0131 bu.<\/p>\n

Turing\u2019in modeli ve yerle\u015fik programlama yakla\u015f\u0131mlar\u0131, Newton fizi\u011fine g\u00f6re i\u015fleyen bir d\u00fcnyay\u0131 esas almaktad\u0131r. Acaba kuantum fizi\u011finin bu yeni ilgin\u00e7 \u00f6zelliklerinden daha h\u0131zl\u0131 hesaplama yapmak i\u00e7in yararlan\u0131labilir mi? A\u015f\u0131lmas\u0131 g\u00fc\u00e7 kimi teknik engeller s\u00f6z konusu olsa da \u00e7o\u011fu uzman \u201ckuantum bilgisayarlar\u0131\u201dn\u0131n g\u00fcn\u00fcn birinde in\u015fa edilebilece\u011fini d\u00fc\u015f\u00fcn\u00fcyor. Hen\u00fcz ortada olmamalar\u0131na kar\u015f\u0131n bu bilgisayarlara \u00f6zg\u00fc algoritmalar\u0131n nas\u0131l kurulabilece\u011fini d\u00fc\u015f\u00fcnebilmemiz i\u00e7in ise yine bir bi\u00e7imsel modele, yani TM\u2019lerin kuantum fizi\u011fine uygun bir s\u00fcr\u00fcm\u00fcne ihtiyac\u0131m\u0131z var.<\/p>\n

Kuantum Turing makinesi (KTM) modeli bu ama\u00e7la tan\u0131mlanm\u0131\u015ft\u0131r. Standart TM tan\u0131m\u0131nda t\u00fcm bile\u015fenlerin (teybin ve kontrol biriminin) \u015fu ayn\u0131 anda birden fazla durumda olabilen par\u00e7ac\u0131klardan in\u015fa edildi\u011fini d\u00fc\u015f\u00fcn\u00fcn. Bu makine art\u0131k ayn\u0131 anda bir\u00e7ok paralel koldan i\u015flem yapabilir. Fizik yasalar\u0131n\u0131n getirdi\u011fi k\u0131s\u0131tlara uyarak komut repertuar\u0131m\u0131za biraz yukar\u0131da OTM\u2019ler i\u00e7in s\u00f6z\u00fcn\u00fc etti\u011fimizi and\u0131ran \u201c3\/5 genlikle 7 numaral\u0131 komuta, -4\/5 genlikle de 10 numaral\u0131 komuta atla\u201d t\u00fcr\u00fcnden \u201ckuantum dallanma\u201d komutlar\u0131 eklememiz gerekir. (\u201cGenlik\u201d, kabaca \u201colas\u0131l\u0131\u011f\u0131n karek\u00f6k\u00fc\u201d olarak d\u00fc\u015f\u00fcnebilece\u011fimiz ve s\u00f6z konusu paralel i\u015flem kollar\u0131n\u0131n a\u011f\u0131rl\u0131klar\u0131n\u0131 belirleyen bir kuantum kavram\u0131d\u0131r.) KTM\u2019lerin de OTM\u2019ler gibi az olas\u0131l\u0131kla yanl\u0131\u015f yan\u0131t vermelerine g\u00f6z yumal\u0131m.<\/p>\n

Genliklerin eksi de\u011ferler de alabilmesi nedeniyle dikkatle d\u00fczenlenmi\u015f bir KTM hesaplamas\u0131 s\u0131ras\u0131nda kimi paralel kollar birbirlerini \u201cg\u00f6t\u00fcrebilir\u201d ve yanl\u0131\u015f sonuca giden yoldaki kollar\u0131n birbirini g\u00f6t\u00fcrmesi sa\u011flanarak y\u00fcksek olas\u0131l\u0131kla do\u011fru sonucu veren algoritmalar yaz\u0131labilir. Klasik programlamada dengi olmayan bu y\u00f6ntemle, bilinen hi\u00e7bir TM\u2019nin h\u0131zla \u00e7\u00f6zemedi\u011fi, verilen bir tamsay\u0131y\u0131 \u00e7arpanlar\u0131na ay\u0131rma problemi i\u00e7in \u00e7ok h\u0131zl\u0131 bir KTM tasarlanabilmi\u015ftir. \u0130nternet \u00fczerinden \u015fifreli ileti\u015fim protokollerinin \u00e7o\u011fu bu problemin h\u0131zla \u00e7\u00f6z\u00fclemeyece\u011fi varsay\u0131m\u0131na dayand\u0131\u011f\u0131ndan, bu algoritman\u0131n bulunmas\u0131ndan sonra kuantum bilgisayarlar\u0131n\u0131n in\u015fas\u0131 \u00f6ncelikli bir proje haline gelmi\u015ftir. Hatta kim bilir, belki de birisi \u00e7oktan b\u00fcy\u00fck \u00f6l\u00e7ekli bir kuantum bilgisayar\u0131n\u0131 in\u015fa etmi\u015ftir ama habersizce ba\u015fkalar\u0131n\u0131n ileti\u015fimini dinlemek daha \u00e7ok i\u015fine geldi\u011finden bunu ilan etmiyordur?<\/p>\n

B\u00fcy\u00fcl\u00fc TM\u2019ler<\/strong><\/p>\n

Karma\u015f\u0131kl\u0131k kuram\u0131n\u0131n merkez\u00ee sorusuna, yani \u00e7\u00f6zene Clay Matematik Enstit\u00fcs\u00fc\u2019nce bir milyon ABD dolarl\u0131k \u00f6d\u00fcl vaat edilmi\u015f olan \u00fcnl\u00fc \u201cP ve NP Problemi\u201dne bir bakal\u0131m.<\/p>\n

Verilen bir metnin bir problemin kurallara uygun yaz\u0131lm\u0131\u015f do\u011fru bir \u00e7\u00f6z\u00fcm\u00fc olup olmad\u0131\u011f\u0131n\u0131 denetlemek, g\u00f6rece kolay bir i\u015ftir. Ama e\u011fer s\u00f6z konusu metin \u00e7ok uzunsa, s\u0131rf bu nedenden \u00f6t\u00fcr\u00fc, denetlemeye zaman\u0131m\u0131z yetmeyebilir. Problemler k\u00fcmesi bu ba\u011flamda d\u00f6rde ayr\u0131l\u0131r:<\/p>\n

1) \u00c7\u00f6z\u00fcms\u00fcz problemler (Durma Problemi ve hatta daha beterleri).<\/p>\n

2) \u00c7\u00f6z\u00fcm\u00fc olan, ama \u00e7\u00f6z\u00fcm\u00fcn uzunlu\u011funun sorunun uzunlu\u011funa oranla art\u0131\u015f h\u0131z\u0131n\u0131n y\u00fcksekli\u011fi nedeniyle \u00e7\u00f6z\u00fcm oldu\u011fu iddia edilen metinleri genelde yukar\u0131daki anlamda denetleyemeyece\u011fimiz problemler (S\u00f6zgelimi yukar\u0131da XOX oyunu i\u00e7in anlatt\u0131\u011f\u0131m\u0131za benzer \u015fekilde genelle\u015ftirilmi\u015f bir satran\u00e7 oyununda verilen bir tahta ebad\u0131 i\u00e7in kimin kazanan stratejisinin oldu\u011funun hesaplanmas\u0131 b\u00f6yle bir problemdir).<\/p>\n

3) \u00c7\u00f6z\u00fcm\u00fc soru uzunlu\u011funa oranla g\u00f6rece k\u0131sa metinlerle ifade edilebilen, yani verilen bir metnin ger\u00e7ekten o sorunun \u00e7\u00f6z\u00fcm\u00fc olup olmad\u0131\u011f\u0131n\u0131 pratikte denetleyebileceklerimiz (\u00d6rne\u011fin verilen bir karayollar\u0131 haritas\u0131nda her kente sadece bir kez u\u011frayarak t\u00fcm kentleri dola\u015fabilecek bir g\u00fczerg\u00e2h varsa, saptama problemi bunlardand\u0131r, b\u00f6yle bir g\u00fczerg\u00e2h\u0131n mevcut oldu\u011funu iddia eden birisinden size kentleri o s\u0131rayla listelemesini isteyip verdi\u011fi listeyi haritayla kar\u015f\u0131la\u015ft\u0131r\u0131rs\u0131n\u0131z, olur biter).<\/p>\n

4) \u00c7\u00f6z\u00fcm\u00fcn\u00fc ba\u015fkas\u0131ndan istemeye gerek kalmadan kendi imk\u00e2nlar\u0131m\u0131zla makul s\u00fcrede bulabilece\u011fimiz problemler (Yol Bulma Problemi bunlardand\u0131r).<\/p>\n

Yukar\u0131daki listede 3. maddede tan\u0131mlanan problemlerin t\u00fcm\u00fcn\u00fcn k\u00fcmesine NP, 4. maddedekilere de P denir. Bu iki k\u00fcmenin e\u015fit olup olmad\u0131\u011f\u0131 bilinmemektedir ve yan\u0131t her neyse kan\u0131tlayacak ki\u015fiyi bir milyon dolar beklemektedir. (S\u00f6zgelimi 3. maddedeki \u00f6rnekteki G\u00fczerg\u00e2h Problemini kimse size g\u00fczerg\u00e2h\u0131 vermeden ve olas\u0131 t\u00fcm yol se\u00e7imlerini denemeden h\u0131zla \u00e7\u00f6zebilen bir algoritma bulursan\u0131z milyon sizindir; yaln\u0131z uyaray\u0131m, b\u00f6yle bir algoritman\u0131n var olmad\u0131\u011f\u0131n\u0131 san\u0131yorum.)<\/p>\n

P ve NP aras\u0131ndaki ili\u015fkiyi incelemek i\u00e7in yine TM\u2019lere ba\u015fvurulur tabii. P \u201cTM\u2019lerce h\u0131zla \u00e7\u00f6z\u00fclebilen problemler k\u00fcmesi\u201d olarak tan\u0131mlan\u0131r. NP i\u00e7inse standart TM tan\u0131m\u0131na bu kez \u201c\u0130stersen 3 numaral\u0131 komuta, istersen 5 numaral\u0131 komuta atla\u201d gibisinden \u201cbelirlenimci olmayan dallanma\u201dlara el veren \u201cb\u00fcy\u00fcl\u00fc\u201d bir komut t\u00fcr\u00fc ekleyerek olu\u015fturulan \u201cBelirlenimci Olmayan TM\u201d (BOTM) modeli kullan\u0131l\u0131r. Bir BOTM \u00e7al\u0131\u015fmas\u0131 s\u0131ras\u0131nda b\u00f6yle bir komuta gelirse, e\u011fer iki se\u00e7enekten birisi onu \u00e7\u00f6z\u00fcme g\u00f6t\u00fcrecek ise, muhakkak o do\u011fru se\u00e7ene\u011fi se\u00e7er! \u00d6rne\u011fin G\u00fczerg\u00e2h Probleminde verilen harita ger\u00e7ekten aranan \u00f6zelli\u011fe sahip bir g\u00fczerg\u00e2h bar\u0131nd\u0131r\u0131yorsa, bir BOTM belli bir kentten hangi kom\u015fu kente gitmek gerekti\u011fini do\u011fru olarak se\u00e7ecektir. (Bunun ger\u00e7ek hayatta olamayaca\u011f\u0131n\u0131 s\u00f6ylemeye gerek yok elbet.) NP de bu b\u00fcy\u00fcl\u00fc yetene\u011fe sahip \u201cBOTM\u2019lerce h\u0131zla \u00e7\u00f6z\u00fclebilen problemler k\u00fcmesi\u201d olarak tan\u0131mlan\u0131r. Standart TM\u2019ler BOTM\u2019lerin yapt\u0131\u011f\u0131 her i\u015fi yapabilir, s\u00f6zgelimi G\u00fczerg\u00e2h Problemini biz de oturup \u00e7\u00f6zebiliriz, ama bunu bir BOTM kadar az ad\u0131mda yapmay\u0131 bilemiyoruz. E\u011fer san\u0131ld\u0131\u011f\u0131 gibi P NP\u2019ye e\u015fit de\u011filse bu TM\u2019lerin BOTM\u2019leri istenen h\u0131zda taklit edemeyece\u011fi anlam\u0131na gelir zaten.<\/p>\n

\u201cP=NP\u201d ifadesinin do\u011fru mu yanl\u0131\u015f m\u0131 oldu\u011funu neden mi bunca merak ediyoruz? \u00c7\u00fcnk\u00fc bilgisayarlar\u0131n hem \u015fimdi, hem de gelecekte hangi problemleri makul s\u00fcrede \u00e7\u00f6zebilip hangilerinde havlu ataca\u011f\u0131n\u0131 bilmek istiyoruz. Yine do\u011fan\u0131n \u00e7izdi\u011fi bir s\u0131n\u0131r\u0131, bu kez pratikte hesaplayabileceklerimizle hesaplayamayacaklar\u0131m\u0131z aras\u0131ndakini, ke\u015ffetmenin pe\u015findeyiz.<\/p>\n

\"\"
Alan Turing\u2019in b\u00fcst\u00fc.<\/figcaption><\/figure>\n

Daktilo<\/strong><\/p>\n

Turing makinesi ve evrensellik fikri, ortaya konulu\u015fundan y\u0131llar sonra, g\u00fcn\u00fcm\u00fcz bilgisayarlar\u0131nda kullan\u0131lan mimarinin temelini olu\u015fturmakla kalmad\u0131. \u00c7ok basit bir altyap\u0131 ile ba\u015fka sistemlerin \u201czihinleri\u201d de dahil \u00e7evrelerindeki her \u015feyi modelleyip benzetimini yapabilecek sistemlerin m\u00fcmk\u00fcn oldu\u011funun anla\u015f\u0131lmas\u0131, bili\u015fsel bilimcilerin zihnin yap\u0131s\u0131 ve evrimi hakk\u0131ndaki d\u00fc\u015f\u00fcncelerini \u015fekillendirdi. Bug\u00fcn hem canl\u0131lar\u0131n evrilmesinde, hem de beynimizin yeni kavramlar\u0131 \u00f6\u011frenmesindeki s\u0131n\u0131rlar, bu s\u00fcre\u00e7lere denk gelen ve P\u2019nin altk\u00fcmesi olan \u00f6zel bir algoritma t\u00fcr\u00fc \u00e7al\u0131\u015f\u0131larak inceleniyor. Kara deliklerin bilgi s\u0131zd\u0131rmas\u0131na ili\u015fkin \u00f6nemli bir problemin bize hesaplama karma\u015f\u0131kl\u0131\u011f\u0131n\u0131 bir fizik yasas\u0131 olarak g\u00f6rmeyi dayatt\u0131\u011f\u0131n\u0131 savlayan kuramsal fizik\u00e7iler var. Giderek, hesaplaman\u0131n do\u011fan\u0131n temel s\u00fcre\u00e7lerinden biri oldu\u011fu, evreni b\u00fcy\u00fck bir bilgisayar olarak d\u00fc\u015f\u00fcnmemiz gerekti\u011fi s\u00f6ylenir oldu. Bunlar\u0131 Alan Turing\u2019in \u00e7ocukken annesinin masas\u0131nda g\u00f6r\u00fcp hayran oldu\u011fu daktilodan esinlenerek 24 ya\u015f\u0131nda kurgulad\u0131\u011f\u0131 bir modele bor\u00e7luyuz.<\/p>\n

Kaynaklar<\/strong><\/p>\n

1) David Hilbert\u00a0ve\u00a0Wilhelm Ackermann\u00a0(1928),\u00a0Grundz\u00fcge der theoretischen Logik, <\/em>Springer-Verlag.<\/p>\n

2) Alonzo Church, \u201cA note on the Entscheidungsproblem\u201d, Journal of Symbolic Logic<\/em>, 1 (1936), 40-41.<\/p>\n

3) Alan Turing, \u201cOn\u00a0computable numbers, with an application to the Entscheidungsproblem\u201d, Proceedings of the <\/em>London Mathematical Society<\/em>, Series 2, 42 (1936-7), 230-265.<\/p>\n

4) Michael Sipser (2013),\u00a0Introduction to the Theory of Computation<\/em>\u00a0(3 ed.), Cengage Learning.<\/p>\n

5) Stefan Reisch,\u201cGobang ist PSPACE-vollst\u00e4ndig\u201d,\u00a0Acta Informatica,<\/em>\u00a013 (1980), 59-66.<\/p>\n

6) Leonard M. Adleman, Jonathan DeMarrais ve Ming-Deh A. Huang\u201cQuantum Computability\u201d,SIAM Journal on Computing<\/em>, 26:5(1997), 1524-1540.<\/p>\n

7) Peter Shor, \u201cPolynomial-time algorithms for prime factorization and discrete logarithm problems\u201d, SIAM Journal on Computing,<\/em> 26:5 (1997), 1484-1509.<\/p>\n

8) Aviezri S. Fraenkel ve\u00a0David Lichtenstein, \u201cComputing a perfect strategy for n<\/em> x n<\/em> chess requires time exponential in n<\/em>\u201d, Journal of Combinatorial Theory<\/em>, Series A, 31 (1981), 199-214.<\/p>\n

9) Leslie Valiant (2013),\u00a0Probably Approximately Correct, <\/em>Basic Books.<\/p>\n

10) Amanda Gefter, \u201cTheoretical physics: Complexity on the horizon\u201d<\/em>, Nature,<\/em>509 (2014), 552-553.<\/p>\n

11) Seth Lloyd (2007), Programming the Universe<\/em>, Vintage Publishing.<\/p>\n

12) Sara Turing (2012),\u00a0Alan M. Turing<\/em>, Cambridge University Press.<\/p>\n","protected":false},"excerpt":{"rendered":"

Turing makinesi ve evrensellik fikri, ortaya konulu\u015fundan y\u0131llar sonra, g\u00fcn\u00fcm\u00fcz bilgisayarlar\u0131nda kullan\u0131lan mimarinin temelini olu\u015fturmakla kalmad\u0131. Giderek, hesaplaman\u0131n do\u011fan\u0131n temel s\u00fcre\u00e7lerinden biri oldu\u011fu, evreni b\u00fcy\u00fck bir bilgisayar olarak d\u00fc\u015f\u00fcnmemiz gerekti\u011fi s\u00f6ylenir oldu. Bunlar\u0131 Alan Turing\u2019in \u00e7ocukken annesinin masas\u0131nda g\u00f6r\u00fcp hayran oldu\u011fu daktilodan esinlenerek 24 ya\u015f\u0131nda kurgulad\u0131\u011f\u0131 bir modele bor\u00e7luyuz. Alan Turing d\u00fcnyay\u0131 de\u011fi\u015ftiren bir dahiydi. […]<\/p>\n","protected":false},"author":604,"featured_media":24540,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[166,453,1464,25],"tags":[2927,2717,255,326,2928],"class_list":["post-24537","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-129-sayi","category-bilisim","category-dosya","category-matematik","tag-alan-turing","tag-algoritmalar","tag-bilgisayar","tag-kriptoloji","tag-turing-makinesi"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/posts\/24537","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/users\/604"}],"replies":[{"embeddable":true,"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/comments?post=24537"}],"version-history":[{"count":0,"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/posts\/24537\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/media\/24540"}],"wp:attachment":[{"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/media?parent=24537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/categories?post=24537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bilimvegelecek.com.tr\/index.php\/wp-json\/wp\/v2\/tags?post=24537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}