Not: Bu içerik, Dr. Craig Steven Wright tarafından kaleme alınan orijinal makalenin Türkçe çevirisidir. Çeviri, yazarın izni doğrultusunda hazırlanmıştır ve tüm telif hakları Dr. Craig Steven Wright’a aittir.

Orijinal İngilizce metne şu bağlantı üzerinden ulaşabilirsiniz: https://web.archive.org/web/20231204103211/https://craigwright.net/blog/math/infinite-and-unbounded/

Dr. Wright’ın Substack Profili: https://substack.com/@cstominaga

Dr. Wright’ın Twitter (X) Profili: https://x.com/CsTominaga

---

Sonsuz ve Sınırsız

Ne yazık ki, günümüzde kullanılan birçok yaygın terimin anlaşılmamasından kaynaklanan büyük bir sorun vardır. Turing-tamlığı sonsuz bir bant gerektirmez ve Turing’in makalesinde bahsettiği de sonsuz bir bant değildi; sınırsız bir sistemdi. Önemli olarak, tanım gereği, sonsuz bantlı bir Turing makinesi olamaz; sınırsız bantlı olabilir. Sonsuz bir bant, hesaplanabilir bir problemle ilişkili değildir. Hem Church hem de Turing makalelerini yazdıklarında, sözünü ettikleri bilgisayar insandı. Problemleri çözen matematikçi bireye “computer” denirdi. Dolayısıyla aynı türden problemlerden söz ettiğimizde, basit bir algoritmik süreçle hesaplanabilen ve artık bir makinede çalışan basit bir süreç tarafından yaratılıp kullanılabilen problemlerden söz ediyoruz.

İlk olarak hatırlamanız gereken şey, bir Turing makinesinin hesaplanabilir her problemi hesaplayabileceğidir. Tüm algoritmalar hesaplanabilir değildir. Hiç durmayan bir program çalıştırabildiğinizi söylemek bir Turing makinesi yaratmak değildir. Bu aynı zamanda sonsuz bir bant da değildir; sınırsız bir sistemdir. Tanım gereği, herhangi bir sınırsız sistem her zaman sonsuzdan sonsuz derecede küçüktür. Düşündüğünüzde, “sınırsız” olarak çalışan bir süreç, evrenimizde zamanın varlığı boyunca çalışabilecek bir sistem gerektirir. Kabul etmek gerekir ki, hesaplama için çok büyük bir değer gerektirir ve akıl almaz derecede büyüktür. Yine de, sonsuz olmaktan çok uzaktır.

Bir sonraki ve muhtemelen daha önemli bileşen şudur: evrenimizde başka bir sayı hesaplanacaksa, evrenimiz sonsuz olmadığı için, sayıyı hesaplama süresi sonlu olmalıdır. Ne yazık ki, hesaplama kararsız bir problemdir; çünkü matematiğin bir bileşeni durma problemi olarak bilinen şeye yol açmıştır (Turing, 1936; Burkholder, 1987). Değerlerin hesaplanması durmayabilir ve durma problemi çözülemez (Boyer & Moore, 1984). Aynı nedenle, bir Turing makinesinde çalışabilen herhangi bir betiğin bir gün durup durmayacağını belirlemek de uygulanabilir değildir. Tanımı gereği, hesaplanabilir herhangi bir sayı ve dolayısıyla algoritmik olarak çözülebilen herhangi bir değer, sonlu bir zaman içinde sona ermelidir. İnsanların kavrayamadığı şey, Turing makinelerinin algoritmik olarak hesaplanamayan programları çalıştırmadığıdır. Algoritmik çözümü olmayan herhangi bir program, Turing makinesinde çözülebilen bir program değildir. Bunların birçoğu ya başarısız olur ya da daha da önemlisi, bir çözüme asla ulaşmadan süresiz olarak devam eder.

Bitcoin, betik düzeyinde bile Turing-tam bir sistemdir. Bir Turing makinesi, sınırsız bir banda sahip olduğunuzu varsayar. Bizim durumumuzda bu, sınırsız betik boyutu anlamına gelir. Keyfi uzunlukta bir betik verildiğinde, hesaplanabilir her olası algoritmayı çalıştırabilirsiniz. Betik boyutunun hantallaşması önemsizdir. Tüm Turing makineleri verimli değildir. Aslında, Turing makinelerinin temellerinde verimliliği gerektiren hiçbir şey yoktur. Görünüşte oldukça uzun sürede tamamlanacak birçok program çalıştırmak mümkünken, bunları paralel yollarla ya da yaklaşık hesaplama yoluyla optimize etmek yeterli olabilir. Buna karşılık, yalnızca hesaplama açısından zor değil, aynı zamanda uygulanamaz ve çözülemez olan ve olası çözümlerden fazlasını üretmeyen bir dizi program vardır. Bu tür programlar süresiz olarak çalışabilir ve algoritmik sistemlerde asla durmayabilir.

Bitcoin Core’un, Bitcoin’in Turing-tam olduğu yönünde yaptığım yoruma saldırmasının temel nedeni, başlangıçta Bitcoin’e geçici olarak getirilen ve daha sonra BTC içinde daha sinsi biçimlerde uygulanan sınırlamaların getirilmesiyle ilgilidir. Ben Bitcoin’in veri merkezlerinde sonlanacak noktaya kadar büyüyeceğini söylerken, onlar daha sınırlı ayrı bir sistem yaratmak istediler. Sınırlı bir bant, herhangi bir algoritmayı çalıştırabilen bir bant değildir. Başka bir deyişle, sınırlı işlem boyutuyla, sınırsız işlem boyutuyla elde edebileceğiniz hesaplama düzeyine asla ulaşamazsınız. Rogers’ın (1959) gösterdiği gibi, hesaplanamazlığın dereceleri vardır; ancak bu, çoğu durumda bir programın çözülebilir olup olmadığını, çalıştırılana kadar bilmediğimiz gerçeğini ortadan kaldırmaz. Daha da kötüsü, Gaboury’nin (1942) ve daha sonra Rogers’ın (1958) gösterdiği üzere, birçok probleme çözüm bulup bulamayacağımızı bile ele alan bir çözüm yoktur.

Bilgisayar biliminde omega problemi olarak bilinen bir problem vardır (Dantzig, Fulkerson ve Johnson, 1954; Hudzik, 1979). Algoritmalar tasarlamadaki zorluk, kanıtlanabilir biçimde duracak algoritmaların nasıl oluşturulacağını bilememekten kaynaklanır. Omega probleminin sonuçları, bilgisayar hatalarını düzeltmedeki zorluklardan birine yol açar. Omega indirgenemezdir. Rastgele programcıların olasılığını ve o algoritmanın verilen bir girdi için sonunda durup durmayacağını sorarsak, sorunun geçerli olup olmadığını bile her zaman belirleyemeyiz. Bu, fizikte her şeyin teorisi (TOE) problemine bağlıdır. Matematik için aksiyomatik bir temel oluşturamayız; yine de evrenin nasıl çalıştığına dair tek bir temel teori bulabiliriz. Ne yazık ki, hesaplamanın matematiksel temellerini belirleyemediğimiz için, durma problemini çözmeye çalışmak, ne verirsek verelim boş kalacak bir çukurdur (Jacobs, 1890).

Turing, hesaplanabilirlik ve lambda tanımları üzerine aynı konuyu ve ilişkili konuları detaylandıran birden fazla makale yazdı (Turing, 1936; Turing & Church, 1937; Turing, 1937). Bunları okursanız, “‘hesaplanabilir’ sayılar”dan söz ettiğini görürsünüz (Turing, 1936, s. 230); bunlar “ondalık olarak ifadeleri sonlu yollarla hesaplanabilen gerçek sayılar”dır. Pi, aynı tanıma göre Turing-hesaplanabilir bir değer değildir. Bunun yerine, pi’nin sonlu zaman ve uzay içinde elde edilen bir yaklaşık değeri Turing-hesaplanabilir kabul edilebilir.

Pi dâhil farklı sayısal değerlerin hesaplanabilirliği üzerine birçok iyi kaynak vardır. Nies (2009) konuyla ilişkili mükemmel bir araştırma kaynağı sunar ve Miller (2003) gibi diğerleri uygun yardımcı çalışmalar sağlar. Hatta Khoussainov, Slaman ve Semukhin’in (2006) çalışmaları gibi daha az bilinen yazarların eserlerine bile bağlayabilirim; ancak bunu burada yapsaydım, “teknik gevezelik” teşvik etmekle suçlanırdım. Bunun nedeni, bu tür çalışmaların geçerli ve algoritmik ve sözdizimsel olarak ilginç olsa da son derece uzmanlık gerektiren ve hatta bazı yönleriyle ezoterik olmasıdır. Dolayısıyla, ne yazık ki bugün o tavşan deliğine girmeyeceğim.

Turing’in makalesi, Gödel’in (1931) çalışmasına dayanmaktadır. Ne yazık ki, yazarların yazdığı ayrık matematik altyapısına sahip değilseniz, Turing makinesinin tanımı söz konusu olduğunda insanların yaptığı birçok hatadan birini yapmanız muhtemeldir. Örneğin, Turing (1936, s. 230), hesaplanabilir sayıların sınıfının “yine de numaralandırılabilir” olduğunu belirtmiştir. Ancak, Turing makinesinin kendisinin, diğer her şeyin doğru olması için, numaralandırılabilir olması gerektiğini söylememiştir.

Turing, Church’ün (1936) “etkin hesaplanabilirlik” kavramı üzerine yaptığı araştırmayı genişletiyordu. Turing’in belirttiği gibi, etkin hesaplanabilirlik ayrı ayrı tanımlanmış olsa da işlevsel olarak Turing’in “hesaplanabilirlik” kavramına denktir. Aynı nedenle buna Church–Turing problemi denmiştir. Her yazar bir çözüm üretmiştir; Church ilkini türetmiştir.

Hennie (1965), tek bantlı, çevrimdışı bir Turing makinesi kavramını incelemiştir. Böyle bir makine ve bant, gerektiğinde hesaplama için kullanılabilir ve daha sonra tek bir hesaplanabilir sayıyı doğrulamak üzere üretilebilecek biçimde yapılandırılmış olarak oluşturulabilir. Böyle bir makinenin Bitcoin betiğinde nasıl yansıtılacağına bir örnek, daha sonra işlenebilecek bir bant üzerinde herhangi bir dijital sayıyı hesaplayabilen bir dizi kural ve matematiksel süreç oluşturmaktır. Bu nedenle bandı Bitcoin betiğine benzetebiliriz. Aynı şekilde, tek bir işlemi, çevrimdışı derlenip üretilen ancak çevrimiçi olarak, sonlu süre içinde kullanılan tek bir bant gibi hayal edebilirsiniz.

Hartmanis (1968), tek bantlı Turing makinelerinin karmaşıklığı üzerine bir tartışma sunmuştur. Hartmanis, düzenli dizi kümelerinin zaman açısından keskin biçimde sınırlı olduğunu belirtirken, bu tür hesaplama biçimlerini ölçmek için çeşitli hesaplama karmaşıklığı biçimlerinin kullanılabileceğini de göstermiştir. Aynı zamanda, bu tür bantlar için farklı karmaşıklık düzeylerini belirlemek ve bunları çok bantlı makinelerinkilerle karşılaştırmak mümkündür. Böylece çeşitli hesaplama karmaşıklığı biçimleri türetilmiştir. Dolayısıyla artık soru, bir betiğin Turing-tam bir sistem sunup sunmadığı değil, verimli olup olmadığıdır. Elbette tek bantlı bir hesaplama verimsizdir ve önereceğim bir şey değildir; ancak uygulanabilir ve mümkündür.

Shannon (1956), Turing’in mekanik ya da elektrikli bir makine yapma fikrine bakmış ve tanımda bir hata yapmıştır. Ne yazık ki Shannon (1956, s. 157), Turing makinesini “bir kontrol öğesi, bir okuma-yazma kafası ve sonsuz bir bant” gerektiren bir sistem olarak tanımlamıştır. Oysa Turing, Turing makinesinin sonsuz olması gerektiğini söylememiştir; bunu söyleyen Shannon’dır. 1950’ler ve 1960’larda hesaplama konusunda uzmanlaşmış diğerleri de ‘sonsuz’ demeleri gerekirken ‘sınırsız’ ya da ‘sınırlaması olmayan’ terminolojisini kullanmıştır. Akıl almaz derecede büyük bir sayı ile sonsuz bir sayı arasındaki ayrım çoğu insan için önemli değildir. Fizik ve matematikte tartışmaları basitleştirmek için kullanılan erken bir kavram “fiilen sonsuz” olarak adlandırılmıştır. Farmer’ın (1935) bir makalesinde kullanılır; yazar, sistem sonsuz olmasa da değerin “fiilen sonsuz” olduğu varsayılarak yaklaşık bir değerin elde edilebileceğini belirtir.

Shannon mükemmel mühendislik ortaya koymuş olsa da matematikçi değildi. Mühendislik bilgisi ile bilgisayar bilimi ve matematiksel temeller arasındaki fark önemli bir ayrım sağlar; zira Turing (1936, s. 230), “ondalık olarak ifadeleri sonlu yollarla hesaplanabilen gerçek sayıları” hesaplayabilen bir makineden kategorik olarak söz etmiştir. Shannon bir mühendistir. Bir mühendis için sistemin matematiği daha az önemlidir ve sınırsız bir sistem ile sonsuz arasındaki fark görünüşte anlamsızdır; her iki durumda da asla hesaplamayacağınız kadar büyük sayılar söz konusudur.

Turing, hesaplama makinesinin sonlu sayıda sembolden fazlasını yazmadığını belirtmiştir (1936, s. 233). Dolayısıyla makine sınırsızdır, ancak sonsuz değildir. Bu, birçok matematikçi olmayanın kavrayamadığı önemli ve anlamlı bir ayrımdır. Sınırsız bir makineyle ilişkili değer, herhangi bir sonsuz değerden sonsuz derecede küçüktür. Bu nedenle, birçok mühendis “fiilen sonsuz” bir sistem kavramını kullanmış ve bazıları 2^256 değerinin bile tüm pratik amaçlar için sonsuz olduğunu söylemiş olsa da, bu değerler hesaplanabilir ve gerçek anlamda kullanılabilirdir.

Ayrıca, bir zaman noktasında fiilen sonsuz olan değerler, daha sonraki bir tarihte hesaplanabilir hâle gelebilir. Kapsayıcı olmayan kümeler ve sınırlar, sınırsız sistemler ve sonsuz sistemler kavramları önemlidir. Örneğin, mevcut tüm şifreleme (hiç yeniden kullanılmamış tek seferlik pedler dışında) bir son kullanma tarihine sahip olduğu ve sonunda kırılacağı söylenebilir. Bugün insanları nasıl eğittiğimizin sınırları nedeniyle, insanlar gerçekten sonsuz bir sistem ile pratikte sonsuz olan bir sistem arasındaki büyük farkı kavrayamamaktadır. Daha da önemlisi, bir değerin hata oranı ihmal edilebilir ve göz ardı edilebilir olsa da, Lorenz (1961), küçük varyasyonların veri temelli süreçlerin sonuçları üzerinde önemli ya da eşzamanlı olarak önemli etkiler yaratabileceğini göstermiştir (Lorenz, 1956).

Hopcroft ve Ullman (1969, s. 168), bantla sınırlı Turing makinelerini incelemiş ve Shannon’ın sınırsız yerine sonsuz bir çalışma bandı varsayma hatasını takip etmiştir. Matematiksel sınırları olmayan bir sistemden söz ederken sonsuzluk varsayımı yapmak ne yazık ki tembelliktir ve bu şekilde yapılmamalıydı. Çevrimiçi ve çevrimdışı Turing makinelerinin sürümlerini tartıştıklarını ve daha önce bahsettiğim çevrimdışı Turing makinesi durumunda bandın döngüye girmediğinin varsayılabileceğini fark edeceksiniz. Makalelerinde (1969, s. 169), yazarların her girdi için makinenin durduğu varsayımını kaldırdıklarını göreceksiniz. Bu bir makine türü sağlar; ancak tek bir örnekten fazlası değildir ve insanlar bunları olduklarından daha fazlası sanıp evrensel hâle getirir. Burada evrensel bir Turing makinesinden söz etmediğimi unutmayın; o bambaşka bir şeydir.

Diyelim ki makaleyi baştan sona okudunuz. Okursanız, Hopcroft ve Ullman’ın (1969, s. 169) 6’lı bir demet olarak sunduğu belirlenimsiz Turing makinesi tanımının sonlu durumlar ve sonlu semboller kullanılarak oluşturulduğunu göreceksiniz. Dolayısıyla bu sonsuz bir makine değildir. Sınırsız bir sistemde sonlu değerlerin oluşturulması, bandın gerektiğinde genişletilebileceği anlamına gelir. Bu, böyle bir sistemde bandın sonsuz olduğu anlamına gelmez; daha ziyade, bandın sonuna yaklaşıldığında yeni bir bandın eklenebileceği anlamına gelir. Bitcoin betiğine dayalı işlemlerin biçimlendirilmesinde, açılan işlemi depolamak için ek disk alanı gerektirirdi (Dongarra & Hinds, 1979).

İnsanlar sonsuz ve sınırsız terimlerini birbirinin yerine kullansa da, farklı kavramları ifade ederler. Sınırsız bir sistem ile sonsuz bir sistem arasında fark vardır; zira sınırsız bir sistem zorunlu olarak sonludur. Tanımlı sınırları olmasa da büyük ölçüde tanımlanabilirdir; bu, büyük ölçüde tanımlanamaz olan sonsuz bir sistemden farklıdır. Steele’in (1980) belirttiği süreçte, açılmış döngüler kullanılarak bir dizi algoritma oluşturulur. Yazar böylece Knuth’un (1973) çalışmalarının bir kısmını genişletir ve seri makinelerin oluşturulmasını inceler. Baker’ın (1978) çalışması gibi diğer araştırmalar da doğrusal makine uygulamaları için açılmış döngüleri incelemiştir.

Bunu düşünmenin yolu şudur: 100 bant birimi uzunluğunda bir sistem yaratırsınız ve daha fazla alana ihtiyacınız olursa, bunu genişletmek için 100 bant birimlik başka bir sistem eklersiniz. Bunu gerektiği kadar çok kez yapabilirsiniz. Bu, sonlu uzayla sınırlı, sonlu zamanda gerçekleşen bir süreç olarak kalır ve dolayısıyla asla sonsuz olmaz. Modern bilgisayarlar bilgiyi işlerken son derece paralelleştirilmiş olsa da, erken dönem bilgisayarlar seri bantlar kullanarak çalışıyordu. Sonuç olarak, seri makinelerin yerine kayıt makinelerine geçiş, birçok insanın hesaplamanın tek yönlü bir işlev olması gerektiğine inanmasına yol açmıştır. Hatta döngü yapmayan bir sistemin kendi başına bir Turing makinesi sunamayacağına bile inanılmıştır.

Tek yönlü sonlu durumlu otomatlar iyi belgelenmiştir ve uzun yıllardır böyledir (Greibach, 1978). Bazıları araştırmalarını tek yönlü fonksiyonları incelemeye kadar genişletmiştir (Levin, 2003). Diğerleri, ani doğrusal uzay olarak bilinen alanda belirlenimci tek yönlü Turing makinelerinin oluşturulmasını ve bunların nasıl daha verimli yaratılabileceğini incelemiştir (Kutrib vd., 2015). Ancak belki de böyle bir sistemin en ilginç kullanımı, basitleştirilmiş evrensel bir hücresel otomat olarak bilinen şeyi yaratmaktır (Iirgen Albert & Culik II, 1987).

Burada “sonlu uzayda” dediğime dikkat edin; bunu “sonsuz” olan bir süreç olduğunu ima edecek şekilde söylemedim. Ayrım matematiksel değil; “sonlu uzayda” ifadesinin İngilizcedeki “sonsuz” ifadesinden farklı olduğunu not etmektir. Uygulanamaz bir problem çözülemez ve çözümü yoktur. Oysa sınırsız bir problem, yeterli zaman ve bellek alanı verildiğinde hesaplanabilir. Kişisel ilgim olasılıksal tek yönlü Turing makineleri üzerine olmuştur (Santos, 1969; Kaņeps & Freivalds, 1990). Ablayev’in (1996) gösterdiği gibi, bunların hepsinde bu tür sistemler için hesaplama karmaşıklığının alt sınırlarını keşfetmek mümkündür.

Paralelleştirilmiş hesaplama üzerine bir makalede, Juille ve Pollack (1996), yukarıda önerilen tek bantlı işlem türünden daha verimli olacak çok bantlı bir Turing makinesi oluşturma yöntemlerini belgeledi. Burada tek bir işlem kullanmak yerine, birçok işlemi paralel olarak çalıştırır ve yalnızca tek bir yolun çözüm olarak öne çıkarılmasını gerektirirsiniz. Böylece tek bir işlem kullanmaz; bunun yerine çevrimdışı Turing makineleri olarak hesaplanan sınırsız sayıda işlem kullanır ve yalnızca istenen çözümü bulduğu ve problemi doğru hesapladığı (blokzincir dışında) gösterilmiş tek bir işlemi blokzincire kaydedersiniz.

McCarthy (1956, s. 177), tek bir Bitcoin işlemindeki bir Turing makinesi gibi bir sistemin (ve hayır, Bitcoin’i tarif etmiyordu—aynı türden genel hesaplama makinelerini tarif ediyordu) son derece verimsiz olduğunu belirtmiştir. Bu nedenle, Juillé ve Pollack’ın (1996) makalesinde açıklandığı gibi, çözüm tek ve hantal bir işlem bandı oluşturmak yerine, birçok olasılığı eşzamanlı olarak hesaplayan paralelleştirilmiş sistemlerde bulunmalıdır. Bununla birlikte, blokzincirin boyutunu sınırlamaya çalışmadığınız sürece, tek bir işlem ve tek bir işlem içinde yazılabilecek betik, kendi başına Turing-tamdır.

Sonuç

Bitcoin’in Turing-tam olmadığı yönündeki argüman, işlem ve blok boyutu sınırlarına dayanmaktadır. Bu tür sınırlar verildiğinde Bitcoin Turing-tam bir sistem olmazdı; ancak Bitcoin bu şekilde sınırlandırılmak üzere tasarlanmamıştır. Bu nedenle, BTC sistemi Turing-tam olmasa da Bitcoin öyledir. Döngü yapamadığı için bir sistemin Turing-tam olmadığına dair argümanlar yanlıştır. Church–Turing sisteminde, bir hesaplama sürecinin ya da algoritmanın döngü yapması için bir gereklilik yoktur; döngüler bulunmadığında algoritmanın uzunluğu aşırı derecede büyük olabilse bile. Alternatif olarak, birçok küçük işlev paralel olarak çalıştırılabilir. Bitcoin bir yüklem (predicate) sistemi olduğundan, yalnızca doğru yanıtı veren çıktı Bitcoin blokzincirine kaydedilecektir.

Referanslar

Ablayev, F. (1996). Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science, 157(2), 139–159.

Baker Jr, H. G. (1978). List Processing in Real Time on a Serial Computer. Communications of the ACM, 21(4), 280–294.

Boyer, R. S., & Moore, J. S. (1984). A Mechanical Proof of the Unsolvability of the Halting Problem. Journal of the ACM (JACM), 31(3), 441–458.

Burkholder, L. (1987). The halting problem. ACM SIGACT News, 18(3), 48–60.

Church, A. (1936). An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, 58 (1936), 345–363.

Gödel, K. (1931). Über formal unentscheidbare Sätze der „Principia Mathematica“ und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38 (1931), 173–198.

Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a Large-Scale Traveling-Salesman Problem. Journal of the operations research society of America, 2(4), 393–410.

Dongarra, J. J., & Hinds, A. (1979). Unrolling loops in Fortran. Software: Practice and Experience, 9(3), 219–226.

Farmer, F. T. (1935). An Apparatus for Recording Average Amplitudes of Wireless Echoes. Mathematical Proceedings of the Cambridge Philosophical Society. 31(2), 295–302.

Gaboury, J. (1942). On Uncomputable Numbers: The Origins of a Queer Computing. Journal of the New Media Caucus| ISSN, 017X.

Greibach, S. A. (1978). One way finite visit automata. Theoretical Computer Science, 6(2), 175–221.

Hartmanis, J. (1968). Computational complexity of one-tape Turing machine computations. Journal of the ACM (JACM), 15(2), 325–339.

Hennie, F. C. (1965). One-tape, off-line Turing machine computations. Information and Control, 8(6), 553–578.

Hopcroft, J. E., & Ullman, J. D. (1969). Some results on tape-bounded Turing machines. Journal of the ACM (JACM), 16(1), 168–177.

Hudzik, H. (1979). The problem of separability, duality, reflexivity and of comparison for generalised Orlicz-Sobolev spaces\(W_M^ k (\Omega)\). Commentationes Mathematicae, 21(2).

Jacobs, J. (1890). English fairy tales. David Nutt.

Juillé, H., & Pollack, J. B. (1996). Massively Parallel Genetic Programming. Advances in Genetic Programming, 2, 339–357.

Khoussainov, B., Slaman, T., & Semukhin, P. (2006). (Pi^ 0_1)-presentations of algebras. Archive for Mathematical Logic, 45(6), 769–781.

Kaņeps, J., & Freivalds, R. (1990). Minimal nontrivial space complexity of probabilistic one-way Turing machines. International Symposium on Mathematical Foundations of Computer Science, 355–361.

Knuth, D. E. (1973). Art of computer programming, volume 2: Seminumerical algorithms. Addison-Wesley Professional.

Kutrib, M., Provillard, J., Vaszil, G., & Wendlandt, M. (2015). Deterministic One-Way Turing Machines with Sublinear Space. Fundamenta Informaticae, 136(1-2), 139–155.

Iirgen Albert, J., & Culik II, K. (1987). A simple universal cellular automaton and its one-way and totalistic version. Complex Systems, 1, 1–16.

Levin, L. A. (2003). The tale of one-way functions. Problems of Information Transmission, 39(1), 92–103.

Lorenz, E. N. (1956). Empirical Orthogonal Functions and Statistical Weather Prediction. Massachusetts Institute of Technology Department of Meteorology.

Lorenz, E. (1961). Chaos theory.

McCarthy, J. (1956). The Inversion of Functions Defined by Turing Machines. Automata Studies (AM-34), 34, 177–182.

Miller, J. S. (2003). Pi-0-1 classes in computable analysis and topology. https://dl.acm.org/doi/abs/10.5555/935786

Nies, A. (2009). Computability and randomness (vol. 51). OUP Oxford.

Rogers, H. (1958). Gödel numberings of partial recursive functions. The journal of symbolic logic, 23(3), 331–341.

Santos, E. S. (1969). Probabilistic Turing machines and computability. Proceedings of the American mathematical Society, 22(3), 704–710.

Shannon, C. E. (1956). A universal Turing machine with two internal states. Automata Studies (AM-34), 34, 157–166.

Steele Jr, G. L. (1980). Destructive Reordering of CDR-Coded Lists.

Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London mathematical society, 2(1), 230–265.

Turing, A. (1936b). Halting problem. London Mathematical Society.

Turing, A. M. (1937). Computability and λ-definability. The Journal of Symbolic Logic, 2(4), 153–163.

Turing, A. M., & Church, A. (1937). Computability and X-definability. Symbolic Logic, 2.