Apakah mesin Turing menganggap sesuatu yang tak terbatas pada suatu titik?

Dalam pertanyaan sebelumnya Apa sebenarnya algoritma itu? , Saya bertanya apakah memiliki "algoritma" yang mengembalikan nilai fungsi berdasarkan array nilai yang dihitung adalah algoritma.

Salah satu jawaban yang menarik perhatian saya adalah yang ini:

Contoh faktorial masuk ke model perhitungan yang berbeda, yang disebut perhitungan tidak seragam. Mesin Turing adalah contoh model komputasi yang seragam: Ini memiliki deskripsi tunggal, terbatas, dan berfungsi untuk input ukuran besar yang sewenang-wenang. Dengan kata lain, ada TM yang memecahkan masalah untuk semua ukuran input.

Sekarang, kita dapat mempertimbangkan perhitungan sebagai berikut: Untuk setiap ukuran input, terdapat TM (atau perangkat komputasi lain) yang memecahkan masalah. Ini pertanyaan yang sangat berbeda. Perhatikan bahwa satu TM tidak dapat menyimpan faktorial dari setiap integer tunggal, karena TM memiliki deskripsi yang terbatas. Namun, kita dapat membuat TM (atau program dalam C) yang menyimpan faktorial semua angka di bawah 1000. Kemudian, kita bisa membuat program yang menyimpan faktorial semua angka antara 1000 dan 10.000. Dan seterusnya.

Bukankah setiap TM benar-benar memiliki cara untuk mengatasi ketidakterbatasan? Maksudku, bahkan TM dengan deskripsi yang terbatas bahwa komputer faktorial dari sejumlah N melalui algoritma

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

berisi asumsi bahwa TM memiliki "perangkat keras" untuk membandingkan jumlah ukuran arbitrer melalui komparator "<=", dan juga ADDers untuk menambah i hingga nomor arbitrer, terlebih lagi , kemampuan untuk mewakili jumlah ukuran arbitrer.

Apakah saya melewatkan sesuatu? Mengapa pendekatan yang saya sajikan dalam pertanyaan saya yang lain kurang layak sehubungan dengan infinity daripada yang ini?

<=<=$Q$$\Sigma$

<=$|Q|$$|\Sigma|$

Mesin Turing tidak benar-benar "berurusan dengan tak terbatas": mereka berurusan dengan hal-hal terbatas tanpa batas, setidaknya dalam definisi standar mereka. Input adalah string terbatas dan, setelah beberapa langkah terbatas, mesin hanya memeriksa atau menulis ke sejumlah sel pita. Tidak ada batasan pada ukuran input atau jumlah langkah perhitungan tetapi, input terbatas dan, setelah sejumlah langkah terbatas, hanya sejumlah terbatas output yang telah diproduksi.

Saya pikir perbedaan penting untuk dibuat adalah bahwa deskripsi mesin Turing terbatas, seperti input ke mesin, sementara kaset itu digunakan sebagai memori tidak terbatas. TM adalah mesin yang sebagian besar terbatas, yang menggunakan pita hingga. Pertimbangkan rekaman itu terdiri dari sel, di mana setiap sel dapat mengandung nilai tunggal. Input ke TM tertulis di kaset.

Deskripsi TM adalah seperangkat tupel yang terbatas <current state, input, output, move, next state>.

Pada setiap langkah, hal yang harus dilakukan ditemukan dengan mencocokkan kondisi dan input saat ini. Misalnya, kita berada dalam keadaan 0, dan kita membaca 1, jadi kita menemukan tupel yang dimulai <0, 1, ...>kemudian kita menulis nilai baru di sel saat ini, bergerak ke kiri atau ke kanan (saya pikir definisi klasik juga memungkinkan untuk tinggal di sel yang sama juga), dan kemudian berubah ke negara baru.

Jadi, untuk contoh Anda, Anda akan memerlukan deskripsi TM yang sangat besar (jumlah <current state, input, output, move, next state>tupel yang tak terbatas ), atau menyertakan informasi pencarian dalam input ke TM. Saya percaya input ke TM didefinisikan sebagai terbatas. Jadi, itu mungkin bukan sesuatu yang bisa Anda lakukan dengan mesin Turing yang didefinisikan secara klasik.

Contoh Fibonacci, sebaliknya, dapat dihitung dalam biner dengan jumlah tupel terbatas untuk menggambarkan TM, dan memiliki input terbatas.

Singkatnya : Mesin Turing dapat melakukan perhitungan tak terbatas (terbatas) pada data tak terbatas (terbatas) dan menghasilkan hasil tak terbatas (terbatas). Gagasan dasarnya adalah bahwa infinitas tersebut dapat didefinisikan sebagai batas entitas hingga, yang didefinisikan dengan cara yang sesuai secara matematis. Ini adalah dasar dari perhitungan matematika semantik. Jika Anda mempertimbangkan program daripada Mesin Turing, program ini juga dapat berisi struktur data tak terbatas (terbatas). Kasus fungsi yang ditabulasi factsebagai algoritma yang mungkin dianalisis pada akhirnya, sebagai program, atau sebagai model TM, dengan petunjuk mengenai hubungan dengan evaluasi malas terhadap objek tak terbatas.

Dengan lebih banyak detail

Mengenai pertanyaan terakhir Anda, TM tidak menghitung pada angka yang berubah-ubah, tetapi pada representasi simbolik dari angka-angka ini sebagai serangkaian panjang simbol yang mewakili mereka. Modulo encoding yang tepat, memang benar bahwa mereka dapat membandingkan atau melakukan aritmatika dengan angka-angka tersebut melalui representasi ini.

Tetapi pertanyaan aslinya adalah tentang peran tak terhingga dalam Mesin Turing pada umumnya.

Jawaban umum untuk pertanyaan ini adalah bahwa Mesin Turing tidak pernah berurusan dengan tak terhingga. Mereka didefinisikan secara terbatas, dan apa pun yang mereka hitung dihitung dalam waktu yang terbatas pada bagian terbatas dari pita (karenanya pita terbatas yang lebih besar akan cukup). Yang benar adalah bahwa waktu kebutuhan ruang TM tidak terikat, yang tidak sama dengan tak terbatas.

Oleh karena itu, setiap jawaban yang dihitung oleh TM dapat dihitung juga oleh finite-state automaton (FSA), yang "sampai batas tertentu" adalah satu cara untuk melihat tabulasi. Kesulitannya adalah bahwa beberapa ukuran input (hampir selalu seperti itu, jika hanya membaca input) akan melebihi ukuran otomat. Tapi kemudian, kita bisa menggunakan yang lebih besar. Jadi jika kita ingin mempertimbangkan ukuran input tanpa batas, kita memerlukan urutan FSA yang tak terbatas yang dapat melakukan perhitungan. Sebenarnya kita mungkin memerlukan mesin negara-terbatas sedikit lebih kompleks daripada FSA tradisional karena mungkin ada output yang akan dihitung (daripada jawaban ya-tidak), tetapi transduser keadaan terbatas mungkin harus dilakukan.

Jadi, jika kita melihat masalah yang memiliki serangkaian instance yang tak terbatas, seperti menghitung GCD, atau hanya menggunakan aritmatika pada bilangan bulat ukuran acak, kita melihat bahwa infinity kembali kepada kita melalui pintu belakang, karena infinite ini mengatur FSA.

$\pi$

Kemudian lagi, kita dapat menggantinya dengan urutan tak terbatas dari perhitungan terbatas dengan mesin hingga. Tapi apakah kita curang.

Dari sudut pandang fisik, itu yang terbaik yang bisa kita lakukan. Kami hanya tahu bagaimana membangun mesin hingga, setidaknya sesuai dengan keadaan terkini dalam bidang fisika, yang diperkirakan tidak akan banyak berubah pada masalah itu dalam waktu dekat.

Tetapi bagaimana kita dapat menangani ketidakterbatasan itu dengan cara yang konsisten dan dapat ditelusuri dari sudut pandang matematika.

Ketika Anda mempertimbangkan serangkaian FSA yang tak terbatas yang dapat semacam bekerja sama untuk menghitung serangkaian jawaban yang tak terbatas, Anda tidak dapat melakukannya secara sewenang-wenang. Anda memerlukan beberapa perlindungan untuk memastikan bahwa apa yang Anda lakukan masuk akal. Diketahui secara umum bahwa Anda dapat dengan sepele membangun set apa pun dengan penyatuan tak terbatas set reguler, sebenarnya dengan penyatuan tak terbatas set singleton. Jadi, mempertimbangkan serikat pekerja tak terbatas dari automata tanpa batasan apa pun akan membawa Anda ke mana-mana. Anda bahkan mempertimbangkan dalam set automata yang sama yang memberi Anda jawaban yang tidak konsisten.

Yang benar-benar Anda inginkan adalah mendefinisikan gagasan tentang konsistensi. Tapi itu membutuhkan beberapa tindakan pencegahan. Mari kita asumsikan Anda menggunakan urutan automata yang tak terbatas untuk mensimulasikan TM yang menjawab ya atau tidak, atau tidak berhenti. Masalahnya adalah bahwa FSA akan selalu berhenti dengan jawaban, seperti ya atau tidak. Tetapi jika Anda menggunakan FSA yang sebenarnya tidak berukuran cukup besar untuk input yang dipilih, apa yang harus dijawab. Baik ya dan tidak dicadangkan untuk kasus-kasus ketika FSA benar-benar mengakhiri perhitungan TM, dan menggunakan salah satu dari jawaban ini dengan perhitungan yang belum selesai hanya akan menimbulkan kebingungan. Apa yang Anda inginkan adalah jawaban yang mengatakan: " maaf, saya terlalu kecil dan saya tidak tahu. Silakan coba dengan pria yang lebih besar dalam keluarga ". Dengan kata lain Anda menginginkan jawaban seperti meluap , atau tidak tahu$\bot$

Jadi, Anda memerlukan automata yang memiliki 3 jenis status: menerima, tidak menerima, dan tidak ditentukan. Status tidak terdefinisi dapat dipandang sebagai status berdiri untuk bagian yang hilang dari otomat yang memaksa komputasi untuk berhenti. Jadi, ketika perhitungan berhenti, tergantung pada keadaan berhenti itu, Anda mendapatkan jawabannya ya , tidak , atau tidak ditentukan .

Sekarang, Anda melihat bahwa yang Anda inginkan adalah urutan automata yang tak terbatas yang konsisten . Baik ya dan tidak konsisten dengan tidak terdefinisi , tetapi ya tidak konsisten dengan tidak . Kemudian dua automata konsisten ketika mereka memberikan jawaban yang konsisten pada input yang sama.

$\pi$$3.14\bot\bot\bot\bot...$$3.1415\bot\bot\bot\bot...$$\bot.\bot5159\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$\pi$

Saya tidak akan mengembangkan lebih lanjut aspek-aspek teoretis ini, yang agak canggung ketika didasarkan pada Mesin Turing. Intinya adalah bahwa konsep-konsep ini mengarah pada gagasan bahwa domain perhitungan (apakah data atau mesin), membentuk struktur matematika seperti kisi, di mana objek tak terbatas dapat didefinisikan secara memadai sebagai batas urutan peningkatan tak terbatas (yaitu, lebih baik dan lebih baik) dari benda yang terbatas. Mendefinisikan urutan yang tak terbatas membutuhkan beberapa peralatan lebih banyak, dan gagasan tentang kontinuitas. Inilah yang secara mendasar adalah teori semantik Dana Scott, dan ia memberikan pandangan yang agak berbeda tentang konsep komputabilitas.

Kemudian, mesin Turing, atau perangkat formal lainnya yang dapat melakukan "perhitungan tak terbatas" dapat didefinisikan sebagai batas urutan sekuensial pendekatan terbatas mesin, yang lebih baik dan lebih baik didefinisikan. Hal yang sama berlaku untuk data apa pun yang dikomputasi dengan mesin, baik input maupun output.

Dokumen paling sederhana yang pernah saya baca tentang ini adalah satu set catatan kuliah tulisan tangan oleh Dana Scott, sering disebut sebagai catatan kuliah Amsterdam. Tetapi saya tidak dapat menemukannya di web. Setiap penunjuk ke salinan (bahkan tidak lengkap, karena saya memiliki bagian dari itu) akan diterima. Tetapi Anda dapat melihat publikasi awal lainnya oleh Scott seperti Garis Besar Teori Matematika Komputasi .

Kembali ke contoh awal pertanyaan

Konsep pendekatan ini berlaku untuk data serta program. Fungsi factini didefinisikan secara rekursif, yang berarti bahwa itu adalah titik paling tidak tetap dari fungsional yang dapat digunakan untuk menghitung urutan perkiraan konvergensi hingga fact. Urutan fungsi terbatas yang semakin didefinisikan ini menyatu dengan entitas tak terbatas yang disebut fungsi fact.

fact$\bot$

Memang benar bahwa, jika Anda mempertimbangkan model komputasi TM elementer, susunan tak terbatas seperti itu tidak dapat diekspresikan dalam formalisme itu. Itu tidak berarti bahwa itu tidak masuk akal. Mesin Turing dapat memiliki pita kedua yang seharusnya diinisialisasi dengan nilai tabulasi dari beberapa fungsi seperti fact. Itu tidak mengubah kekuatan komputasi TM, selama fungsi itu adalah yang dapat dihitung, yaitu selama tabel dapat diinisialisasi dengan perhitungan tak terbatas dari TM lain yang dapat menghitung semua pasangan nilai-argumen untuk fungsi yang relevan.

Namun dalam praktiknya, Anda tidak dapat menyelesaikan perhitungan tanpa batas. Oleh karena itu cara yang tepat untuk melakukannya adalah dengan menghitung tabel dengan malas, yaitu untuk mengisi entri hanya saat diperlukan. Itulah tepatnya yang dilakukan dengan memoisasi, yang merupakan jawaban yang saya berikan kepada Anda, dengan berbagai pembenaran, untuk pertanyaan Anda sebelumnya.

Inti dari jawaban ini adalah bahwa Mesin Turing dapat meniru apa pun yang dapat kita program, dan kita melakukan perhitungan program pada, dengan dan dari objek tak terbatas.

Ini adalah jawaban kedua yang lebih fokus pada pertanyaan spesifik yang diajukan daripada pada kerangka teori umum yang membenarkan jawaban, dan akan sangat dibutuhkan untuk menjawab judul pertanyaan yang lebih umum. Ini sepenuhnya kompatibel dengan jawaban saya sebelumnya untuk pertanyaan OP, baik Apa itu algoritma? dan Apakah mesin turing mengasumsikan sesuatu yang tak terbatas pada titik tertentu? , jawaban di mana saya lebih mengembangkan konteks teoretis. Ini dapat dilihat sebagai menjawab kedua pertanyaan.

Mesin Turing memang memiliki kemampuan untuk menangani ketidakterbatasan , seperti halnya semua model komputasi Turing yang lengkap, meskipun hanya dengan tak terhingga banyaknya. Masalah kita adalah kita hanya dapat mengamati sebagian dari ketidakterbatasan ini, tetapi kita harus mempertimbangkan keseluruhannya karena bagian yang mungkin kita amati tidak terikat.

Masalah lainnya adalah kita hanya bisa berurusan dengan entitas yang ditentukan secara spesifik. Sebenarnya, seluruh struktur sains yang kita kenal jatuh jika kita menganggap entitas yang tidak ditentukan secara spesifik, karena menjadi tidak mungkin untuk memeriksa konsistensi definisi, bahkan mengetahui apa definisi itu, karena kita hanya dapat mengakses sebagian dari mereka dalam waktu yang terbatas.

Mungkin ada masalah mendasar lain yang agak mirip dengan fakta bahwa penutupan di bawah serikat tanpa batas mendefinisikan set apa pun yang Anda inginkan, kecuali jika Anda dapat secara terbatas membatasi dengan tepat apa yang diizinkan dalam serikat tersebut. Tetapi saya tidak yakin saya sepenuhnya memahami masalah ini.

Seperti yang saya katakan, mesin Turing memang memiliki kemampuan untuk menangani ketidakterbatasan . Saya menentang jawaban tervvotasikan baik lainnya dari beberapa pengguna rep tinggi, yang harus tahu apa yang mereka bicarakan tentang topik dasar.

Masalahnya adalah bahwa Turing memilih model perhitungan yang sangat dasar untuk mencapai tujuan teoretisnya. Lebih sederhana, semakin baik. Ini adalah model komputasi yang lebih maju / canggih seperti bahasa pemrograman untuk pemrograman: sesuatu yang sangat tidak jelas di mana Anda tidak dapat mengenali konsep apa pun yang masuk akal dalam pemrograman tingkat tinggi. Faktanya adalah, seperti bahasa mesin, TM dapat meniru jauh lebih banyak daripada yang bisa mereka ekspresikan secara langsung.

$23{rd}$ Tetapi itu masih akan sering diimplementasikan sebagai perhitungan tak terbatas yang secara artifisial dihentikan ketika jawaban yang tepat diperoleh.

Sebenarnya, semua pengguna yang menyatakan bahwa semuanya terbatas tetapi tidak terikat dalam TM cukup berhati-hati untuk menambahkan bahwa mereka menganggap Mesin Turing dalam definisi standar mereka . Masalahnya adalah bahwa definisi standar hanyalah alat untuk menyederhanakan teori, tetapi cukup banyak tidak relevan ketika mencoba memahami struktur komputasi.

Sebenarnya, satu-satunya hal yang penting dalam perhitungan adalah bahwa segala sesuatu harus ditentukan dengan cara yang dapat dihitung, bukan bahwa itu terbatas .

Kami mengasumsikan bahwa mesin turing harus menjadi objek yang terbatas. Tapi itu tidak benar. Anda dapat menentukan model mesin Turing menggunakan rekaman kedua yang hanya baca, dan berisi fungsi yang ditabulasikan untuk semua nilai integer, tanpa ikatan apa pun. Itu tidak terbatas. Tapi itu tidak memberi Anda kekuatan komputasi tambahan selama konten rekaman itu ditentukan secara computatbly (komputabilitas menyiratkan bahwa itu ditentukan secara spesifik). Kaset ekstra bisa diganti dengan mesin TM yang tertanam di yang lain, dan akan memberikan jawabannya, alih-alih mencari mereka di kaset tambahan. Dari level yang lebih tinggi, perbedaannya tidak terlihat.

Dari sudut pandang realisasi praktis, kita dapat memiliki fact mesin turing yang menghitung faktorial dan menaburkannya pada kaset tambahan, sementara TM lainnya akan menggunakan faktorial yang ditabulasi dari rekaman ekstra, hanya menunggu TM pertama setiap kali tabulasi memiliki beberapa yang masih hilang masuk. Tetapi mesin kedua mengasumsikan bahwa isi rekaman itu pada akhirnya tidak terbatas. Mesin tabulasi bahkan tidak harus bekerja sepanjang waktu, tetapi harus melanjutkan perhitungan setiap kali data diminta dari tabel dan tidak ditemukan di sana.

Kembali ke pertanyaan, perbedaan utama antara bilangan bulat tak terbatas dan tabel tak terbatas hanya bahwa bilangan bulat terbatas, tidak terikat tetapi sepenuhnya dihitung dalam waktu terbatas. Tabel tak terbatas dihitung tanpa batas, terbatas tetapi masih terus berkembang hingga tak terhingga. Itu bukan masalah, tetapi perbedaan. Objek yang tak terbatas hanya dapat diakses melalui perkiraan terbatas, ... tetapi mereka tidak terbatas. Dalam hal ini, bilangan irasional yang dapat dikomputasi adalah objek tak terhingga, setidaknya untuk representasi mereka sebagai bilangan biner.

Semua algoritma didefinisikan dalam konteks beberapa teori matematika. Dan pencarian tabel bersama-sama dengan tabel tak terbatas adalah algoritma. Tetapi ini adalah suatu algoritma dalam teori matematika yang memiliki serangkaian aksioma tak terbatas yang didefinisikan secara terbatas yang menentukan secara luas (bukan secara intensif) nilai-nilai fungsi yang diautomasinya untuk setiap argumen bilangan bulat. (lihat jawaban saya untuk pertanyaan Anda sebelumnya ). Maka itu selalu sah untuk melakukannya, karena Anda selalu dapat menambahkan pernyataan yang terbukti benar untuk aksioma teori.

Pernyataan usul, sebagaimana direproduksi dalam pertanyaan Anda saat ini, menurut pendapat saya salah (meskipun semuanya juga masalah definisi). Kesimpulannya dalam jawabannya , bahwa Anda tidak mereproduksi, adalah bahwa penggunaan tabel tak terbatas tidak dapat dianggap sebagai algoritma karena hanya dapat diimplementasikan oleh model perhitungan yang tidak seragam, oleh kumpulan mesin yang berbeda, dan karenanya menggunakan " tidak memiliki deskripsi hingga yang dapat diimplementasikan untuk menyelesaikan masalah" keseluruhan "untuk ukuran input apa pun$\pi$

Cara entitas tak terbatas seperti itu dihitung dalam praktiknya adalah melalui evaluasi yang malas , menghitung bagian apa saja yang dibutuhkan setiap saat, dan melanjutkan perhitungan untuk sebagian sisanya ketika dibutuhkan lebih banyak lagi. Itulah yang diusulkan di atas dengan factmesin menghitung faktorial malas untuk disimpan dalam sebuah tabel, setiap kali lebih banyak data diperlukan dari tabel.

Di satu sisi, yang tampaknya membenarkan pernyataan (dalam jawaban DanielV ) bahwa ruang kode harus terbatas, karena evaluasi malas akan benar-benar didasarkan pada beberapa kode terbatas. Tetapi komputabilitas adalah permainan encoding yang luas, sehingga, antara lain, membedakan kode dari data selalu cukup banyak di mata yang melihatnya. Memang, banyak bahasa pemrograman modern tidak membuat banyak perbedaan antara spesifikasi nilai intensional dan ekstensional , dan Denotational Semantic tidak benar-benar membedakan "2 + 2" dari "4". Semantik benar-benar yang sedang kita bicarakan ketika mengajukan pertanyaan seperti " Apa itu X ? ".

Pandangan tentang keterbatasan kode ini, juga dilihat sebagai statis, adalah alasan lain mengapa tabel tak terbatas (dianggap sebagai bagian dari kode) tidak terlihat pada pijakan yang sama dengan bilangan bulat tanpa batas yang digunakan sebagai data. Tapi itu adalah ilusi lain yang tidak bertahan dari praktik pemrograman yang dikenal dalam metaprogramming , bahasa refleksif, dan penggunaan evalfungsi. Dalam bahasa-bahasa tersebut, kode dapat diperpanjang tanpa batas oleh program yang sedang berjalan itu sendiri, selama komputer sedang berjalan. Memang orang dapat mempertimbangkan Mesin Turing yang mengubah aturan transisi mereka sendiri, meningkatkan jumlah mereka tanpa terikat. Itu cukup dekat dengan cara mesin Universal Turing bekerja.

Saat mendesain kerangka kerja teoretis, selalu ada ketegangan antara kesederhanaan dan perspektif atau ekspresivitas. Kesederhanaan membuat analisis kerangka seringkali lebih sederhana, terutama ketika datang untuk membuktikan properti tertentu atau menguranginya ke kerangka kerja lain. Tetapi seringkali tidak nyaman untuk mengekspresikan konsep tingkat tinggi yang kemudian harus dikodekan. Kami tidak memprogram dengan Mesin Turing, tetapi dengan bahasa tingkat tinggi yang jauh lebih ekspresif dan tajam, dan pada saat yang sama dapat menghapus beberapa hambatan seperti perbedaan antara kode dan data, berdasarkan kesetaraan semantik. Mesin Turing tampak sederhana, tetapi dapat melampaui definisi dasarnya.

Jawaban singkatnya: tidak . Mesin Turing tidak mengasumsikan sesuatu yang tak terbatas pada titik mana pun.

Ini adalah salah satu alasan mengapa mereka valid sebagai model perhitungan. Tidak masuk akal untuk menggambarkan komputasi sebagai sesuatu yang dilakukan oleh perangkat tanpa batas.

Namun, operasi mereka mungkin tidak terbatas: itu mungkin tidak berakhir. Ini adalah alasan lain mengapa mereka valid sebagai model perhitungan. Perangkat yang hanya dapat melakukan operasi yang dijamin selalu berakhir tidak dapat mengungkapkan semua perhitungan yang mungkin.

Terlebih lagi: operasi membutuhkan memori tidak terbatas : sementara jumlah aktual dari memori yang digunakan selalu terbatas, ia dapat tumbuh besar secara sewenang-wenang. Jadi, Anda tidak dapat memasok semua memori yang diperlukan operasi apa pun sebelumnya. Perangkat yang hanya dapat melakukan operasi yang dijamin tidak akan pernah menggunakan lebih dari jumlah memori tetap tertentu tidak dapat mengungkapkan semua perhitungan yang mungkin.

"berpikir di luar kotak" dan menggeneralisasi pertanyaan ini yang benar-benar menyentuh abstraksi mesin-mesin Turing, dan muncul dengan sudut pandang yang berbeda belum dijawab: ya, mesin-mesin Turing memiliki beberapa aspek intrinsik dari "mengasumsikan infinitas" hanya sebagai konsep intrinsik untuk matematika. TM adalah abstraksi mesin fisik. konsep fisik Waktu dan Ruang sengaja digunakan dalam teori TM tetapi sebagai abstraksi, namun juga dengan aspek-aspek rekan nyata mereka.

singkatnya TM mungkin dapat berjalan selamanya dalam teori , alias masalah yang terputus - putus . rekaman itu tidak terbatas tetapi hanya jumlah terbatas yang dapat ditulis pada waktu tertentu. TM yang berjalan selamanya pada dasarnya mengasumsikan bahwa waktu dan ruang tidak terbatas, yaitu "tak terbatas". sebenarnya ada hierarki Waktu dan Ruang / "kontinum" yang tak terbatas.

tetapi tidak ada realisasi fisik dari konsep abstrak ini dimungkinkan dengan asumsi alam semesta fisik dibatasi (ruang, waktu, materi, yang terakhir agak analog dengan "simbol" atau "tinta" di mesin Turing). agak serupa / analog, dalam fisika kadang-kadang alam semesta dianggap tidak terikat / tak terbatas, tetapi hanya sebagai abstraksi. untuk membalik ini, itu juga mengapa "pemodelan" komputer modern sebagai mesin Turing itu sendiri merupakan abstraksi, karena komputer hanya dapat memiliki memori yang terbatas dll.

perbandingan lain yang bermanfaat adalah garis bilangan dalam matematika. garis bilangan tidak terbatas, tetapi menunjukkan angka terbatas. setiap angka pada garis bilangan mewakili jumlah terbatas, tetapi ada jumlah tak terbatas dari jumlah terbatas ini. pita mesin Turing memiliki kemiripan yang kuat dengan konsep garis bilangan dari matematika. Turing dapat dengan mudah mendefinisikannya sebagai hanya tak terbatas dalam satu arah, tetapi ia mendefinisikannya sebagai tak terbatas di kedua arah, seperti garis bilangan matematika, dengan posisi negatif "kiri" pada kaset dan posisi positif "kanan".