Yapay zeka teknolojilerinden güç alan bilgisayarlar, günümüzde ikna edici konuşmalar yapmak insanlarla, şarkı bestelemek, boya resimlerioynamak satranç ve gitVe hastalıkları teşhis etmekteknolojik hünerlerinden sadece birkaç örnek vermek gerekirse.
Bu başarılar, hesaplamanın sınırları olmadığını belirtmek için alınabilir. Durumun böyle olup olmadığını görmek için, bir bilgisayarı neyin güçlü kıldığını anlamak önemlidir.
Bir bilgisayarın gücünün iki yönü vardır: donanımının saniyede yürütebildiği işlem sayısı ve çalıştırdığı algoritmaların verimliliği. Donanım hızı fizik yasalarıyla sınırlıdır. Algoritmalar – temel olarak talimat setleri – insanlar tarafından yazılır ve bilgisayar donanımının yürütebileceği bir dizi işleme dönüştürülür. Bir bilgisayarın hızı fiziksel sınıra ulaşabilse bile, algoritmaların sınırları nedeniyle hesaplama engelleri devam eder.
Bu engeller, bilgisayarların çözmesi imkansız olan sorunları ve teorik olarak çözülebilen ancak pratikte günümüz bilgisayarlarının hayal edilebilecek en güçlü sürümlerinin bile yeteneklerinin ötesinde olan sorunları içerir. Matematikçiler ve bilgisayar bilimcileri, hayali bir makinede deneyerek bir sorunun çözülebilir olup olmadığını belirlemeye çalışırlar.
G/O Media komisyon alabilir
Bağımlılık danışmanlığı
Güvenli Liman Sağlık
Herkes için erişilebilir
Safe Haven, esnek ve bireyselleştirilmiş madde bağımlılığı tedavisi, özellikle opioid ve alkol bağımlılığı ile ihtiyaçlarınıza öncelik verir.
Hayali bir bilgisayar makinesi
Turing makinesi olarak bilinen modern algoritma kavramı, 1936’da İngiliz matematikçi tarafından formüle edildi. Alan Turing. Aritmetik hesaplamaların kağıt üzerinde kalemle nasıl yapıldığını taklit eden hayali bir cihazdır. Turing makinesi, günümüzdeki tüm bilgisayarların dayandığı şablondur.
Manuel olarak yapıldığında daha fazla kağıda ihtiyaç duyacak hesaplamalara uyum sağlamak için, bir Turing makinesi sınırsız olduğu varsayılır. Bu, her biri ya boş olan ya da bir simge içeren hayali bir sınırsız şeride ya da karelerden oluşan “şeride” eşdeğerdir.
Makine sonlu bir dizi kural tarafından kontrol edilir ve banttaki bir ilk sembol dizisiyle başlar. Makinenin yapabileceği işlemler komşu kareye gitmek, sembol silmek ve boş kareye sembol yazmaktır. Makine, bu işlemlerin bir dizisini gerçekleştirerek hesaplama yapar. Makine bittiğinde veya “durduğunda”, bantta kalan semboller çıktı veya sonuçtur.
Turing makinesi nedir?
Bilgi işlem genellikle evet veya hayır cevabı olan kararlarla ilgilidir. Benzer şekilde, bir tıbbi test (sorun türü), bir hasta örneğinin (sorunun bir örneği) belirli bir hastalık göstergesine (evet veya hayır yanıtı) sahip olup olmadığını kontrol eder. Bir Turing makinesinde dijital biçimde temsil edilen örnek, sembollerin ilk dizisidir.
Olumlu ya da olumsuz her örnek için durup, örneğin hangi yanıtı verdiğini doğru bir şekilde belirleyen bir Turing makinesi tasarlanabilirse, bir sorun “çözülebilir” olarak kabul edilir.
Her sorun çözülemez
Pek çok problem bir Turing makinesi kullanılarak çözülebilir ve bu nedenle bir bilgisayarda çözülebilirken, diğerleri çözülemez. Örneğin, Çinli Amerikalı matematikçi tarafından formüle edilen döşeme probleminin bir çeşidi olan domino problemi Hao Wang 1961’de çözülemez.
Görev, tüm ızgarayı kaplamak için bir dizi domino kullanmak ve çoğu domino oyununun kurallarını izleyerek, bitişik dominoların uçlarındaki pip sayısını eşleştirmektir. Bir dizi domino ile başlayıp, setin ızgarayı tamamen kaplayıp kaplamayacağını belirleyen bir algoritma olmadığı ortaya çıktı.
makul tutmak
Bir dizi çözülebilir problem, makul bir süre içinde duran algoritmalar tarafından çözülebilir. Bunlar “polinom zamanlı algoritmalar” verimli algoritmalardır, yani bunların örneklerini çözmek için bilgisayarları kullanmanın pratik olduğu anlamına gelir.
Bu tür algoritmaları bulmak için devam eden yoğun çabalara rağmen, çözülebilir diğer binlerce problemin polinom zamanlı algoritmalara sahip olduğu bilinmemektedir. Bunlar, Gezgin Satıcı Problemini içerir.
Gezgin Satıcı Problemi, bazı noktaları doğrudan bağlantılı olan bir nokta kümesinin, grafik adı verilen, herhangi bir noktadan başlayan ve diğer her noktadan tam olarak bir kez geçen ve orijinal noktaya geri dönen bir yola sahip olup olmadığını sorar. Bir satıcının, bir mahalledeki tüm evleri tam olarak bir kez geçen ve başlangıç noktasına geri dönen bir rota bulmak istediğini hayal edin.
Birkaç varış noktasının ötesine geçtiğinizde Gezgin Satıcı Problemi hızla kontrolden çıkar.
adı verilen bu problemler NP-tamamlandıbağımsız olarak formüle edildi ve 1970’lerin başında iki bilgisayar bilimcisi, Amerikalı Kanadalı tarafından var olduğu gösterildi. Stephen Cook ve Ukraynalı Amerikalı Leonid Levin. Çalışması birinci olan Cook, bu çalışmasıyla bilgisayar biliminin en yüksek derecesi olan 1982 Turing Ödülü’ne layık görüldü.
tam olarak bilmenin maliyeti
NP-tamamlanmış problemler için en iyi bilinen algoritmalar, esas olarak tüm olası cevaplardan bir çözüm arıyor. Birkaç yüz noktalık bir grafik üzerindeki Gezgin Satıcı Probleminin bir süper bilgisayarda çalışması yıllar alırdı. Bu tür algoritmalar verimsizdir, yani matematiksel kısayollar yoktur.
Gerçek dünyada bu sorunları ele alan pratik algoritmalar yalnızca yaklaşık değerler sunabilir. yaklaşımlar gelişiyor. yapabilen verimli polinom zamanlı algoritmalar olup olmadığı NP-tam problemlerini çöz arasında yedi milenyum açık problemler Clay Mathematics Institute tarafından 21. yüzyılın başında yayınlanmıştır, her biri 1 milyon ABD Doları ödül taşımaktadır.
Turing’in Ötesinde
Turing’in çerçevesinin ötesinde yeni bir hesaplama biçimi olabilir mi? 1982 yılında Amerikalı fizikçi Richard Feynmanbir Nobel ödüllü, kuantum mekaniğine dayalı hesaplama fikrini ortaya attı.
Kuantum bilgisayar nedir?
1995 yılında, Amerikalı bir uygulamalı matematikçi olan Peter Shor, bir kuantum algoritması sundu. polinom zamanında çarpan tamsayıları. Matematikçiler, bunun Turing’in çerçevesindeki polinom zamanlı algoritmalarla çözülemeyeceğine inanıyor. Bir tam sayıyı çarpanlara ayırmak, tam sayıyı bölebilecek 1’den büyük daha küçük bir tam sayı bulmak anlamına gelir. Örneğin, 688,826,081 tam sayısı daha küçük bir tam sayı olan 25,253 ile bölünebilir çünkü 688,826,081 = 25,253 x 27,277.
denilen büyük bir algoritma RSA algoritmasıağ iletişimini güvence altına almak için yaygın olarak kullanılan, büyük tamsayıları çarpanlara ayırmanın hesaplama zorluğuna dayanır. Shor’un sonucu, kuantum hesaplamanın, gerçek olması durumunda, siber güvenliğin manzarasını değiştir.
Tamsayıları çarpanlara ayırmak ve diğer sorunları çözmek için tam teşekküllü bir kuantum bilgisayar inşa edilebilir mi? Bazı bilim adamları bunun olabileceğine inanıyor. Dünyanın dört bir yanındaki birkaç bilim adamı grubu bir tane oluşturmak için çalışıyor ve bazıları şimdiden küçük ölçekli kuantum bilgisayarlar yaptı.
Bununla birlikte, daha önce icat edilen tüm yeni teknolojiler gibi, kuantum hesaplama ile ilgili yeni sınırlar getirecek sorunların ortaya çıkması neredeyse kesindir.
Jie Wang bir Pşirketinde Bilgisayar Bilimleri profesörü UMass Lowell.
Bu makale şu adresten yeniden yayınlanmıştır: Konuşma Creative Commons lisansı altında. Okumak orijinal makale.