Perhitungan tak terbatas dalam waktu yang terbatas

Ini mungkin pemikiran yang konyol, tetapi misalkan kita memiliki komputer yang diprogram untuk melakukan urutan perhitungan yang tak terbatas dan anggaplah perhitungan membutuhkan detik untuk diselesaikan. Kemudian komputer ini dapat melakukan perhitungan dalam jumlah tak terbatas dalam waktu yang tidak terbatas. $i^\text{th}$ $1/2^i$

Mengapa ini tidak mungkin? Apakah ada batasan yang lebih rendah pada berapa lama waktu yang dibutuhkan untuk melakukan perhitungan non-sepele?

computability computation-models dsaxton
sumber

Konsep terkait, perhitungan tanpa batas menggunakan energi terbatas: Kecerdasan abadi Dyson .

Peter

Jawaban:

"Jenis" komputer ini dikenal sebagai Mesin Zeno . Model komputasinya termasuk dalam kategori yang disebut Hypercomputation . Model komputasi hiper adalah abstraksi matematis, dan karena cara mereka didefinisikan untuk bekerja, mereka secara fisik tidak mungkin.

Ambil Mesin Zeno Anda misalnya. Jika kita membayangkan Mesin Zeno menjadi mesin penghitung apa pun, apakah itu menggunakan sempoa atau sirkuit terintegrasi tidak masalah. Katakanlah data program yang digunakan oleh mesin diumpankan ke dalamnya dengan rekaman simbol yang sangat panjang (seperti Mesin Turing).

Tentu saja, kita tahu dari matematika bahwa:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n$

yang kita katakan sama dengan . Jadi perhitungan harus selesai dalam 1 detik karena jumlah benar-benar bertemu. $1$

Tetapi konvergensi ini, tentu saja, bergantung pada menuju (dan mencapai) ketidakterbatasan. Dalam pengertian fisik, ini berarti bahwa ketika waktu yang dibutuhkan untuk setiap perhitungan semakin kecil, "read head" dari mesin hitung harus melakukan zip sepanjang simbol dalam rekaman lebih cepat dan lebih cepat. Pada titik tertentu, kecepatan ini akan melebihi kecepatan cahaya. $n$

Jadi, menjawab pertanyaan kedua Anda, batas terendah absolut yang mungkin ada pada perhitungan mungkin berada pada urutan waktu Planck, mengingat kecepatan cahaya sebagai faktor pembatas utama dalam model perhitungan teoretis, tetapi masuk akal secara fisik.

Teori Segalanya
sumber

Ada juga kebutuhan energi untuk setiap operasi, membalik sedikit

kali membutuhkan beberapa kali lipat lebih banyak energi daripada di matahari kita

2^{256}

$2^{256}$

ratchet freak

Apakah program ini: 10: GOTO 10 selesai di Mesin Zeno?

Cano64

Dalam istilah yang lebih sederhana, matematika mengandaikan bahwa "perhitungan" dapat dibagi dalam ruang lingkup yang tak terbatas. Namun itu tidak terjadi pada mesin fisik mana pun, karena Anda akhirnya mencapai titik di mana Anda telah mencapai unit kerja terkecil yang dapat dilakukan mesin tersebut. Tidak mungkin untuk melanjutkan membagi kembali perhitungan setelah titik itu, meskipun matematika memungkinkan Anda untuk melakukannya. Dengan kata lain, mesin itu hancur jauh sebelum Anda benar-benar mendekati akhir dari rangkaian perhitungan yang tak terbatas. Pada titik tertentu waktu per perhitungan berhenti berkurang, dan Anda akhirnya membutuhkan waktu tak terbatas.

Agustus

@ Cano64 Saya rasa tidak. Saya percaya kriteria untuk decidability dalam hypercomputation adalah bahwa jumlah waktu dari perhitungan benar-benar bertemu.

Theory of Everything

Waktu yang diperlukan untuk perhitungan primitif dibatasi oleh kecepatan cahaya dan ukuran atom, sejauh yang kita pahami fisika pada hari ini, 15 September 2015.

Unit perhitungan perlu dibangun dari sesuatu yang tidak berukuran nol (atom) dan agar perhitungan dapat bekerja, listrik atau cahaya akan perlu di-zip di atasnya, yang akan dibatasi oleh berapa lama waktu yang dibutuhkan untuk meng-zip melintasi non-nol jarak-nol.

Dave Clarke
sumber

Salah satu contoh nyata dalam sejarah sains yang mendorong batasan baru adalah magnetoresistance raksasa , penemuan pemenang Hadiah Nobel yang memungkinkan kepadatan data pada hard drive yang sebelumnya dianggap mustahil. Ada banyak, lebih banyak lagi jika Anda kembali; coba jelaskan kemungkinan "smartphone" kepada seseorang dari 1500 Masehi. (Mereka mungkin hanya membakar Anda sebagai penyihir, jadi berhati-hatilah.) Jadi saya pikir kita tidak boleh berasumsi bahwa pengetahuan kita saat ini tentang fisika menginduksi batasan keras pada apa yang mungkin.

Raphael

-1

$\Sigma_{n=1}^\infty (\frac{1}{2})^n$ $1$

$\frac{1}{2}$ $\frac{1}{4}$ $\frac{3}{4}$

$c_1$ $c_1$

Sunting : Seperti dicatat oleh @aroth, analogi ini mengasumsikan bahwa kita dapat terus membagi air; bahwa tidak ada atom terkecil yang tak terpisahkan. Yang memunculkan poin menarik (saya pikir) bahwa kita juga harus mengasumsikan waktu untuk dapat dibagi secara sewenang-wenang agar perhitungannya selesai dalam waktu yang terbatas.

epa095
sumber

"Dan sama jelasnya Anda akan selalu memiliki lebih banyak air di ember biru untuk dituangkan" - Belum tentu. Dengan peralatan penuangan yang cukup tepat Anda akhirnya akan mencapai titik di mana ada 2 molekul air dalam ember biru. Lalu 1 molekul. Kemudian Anda menuangkan molekul terakhir, atau tidak. Atau Anda memecahnya menjadi atom-atom dasarnya, tetapi kemudian tidak lagi air (atau dituangkan di STP). Intinya adalah, Anda akan turun ke molekul air terakhir sebelum Anda sampai ke akhir deret tak hingga, sehingga tidak akan "selalu" ada air di ember biru.

aroth

@aroth: ya benar, agar analogi ini bekerja, Anda harus menganggap air sebagai "kepadatan" yang memuaskan, semacam "selalu dapat dibagi". Maksud Anda menarik karena menyoroti sesuatu yang penting; agar perhitungan selesai dalam waktu yang terbatas, waktu juga harus padat / selalu dapat dibagi. Jika ada jumlah waktu terpendek, satuan atom yang tidak dapat dibagi, maka perhitungan tak terhingga akan memakan waktu tak terbatas (atau setiap perhitungan tidak boleh memakan waktu masing-masing setelah beberapa titik).

epa095

\sum_{i = 1}^{\infty} 2^{- i}

$\sum_{i=1}^\infty 2^{-i}$

2^{- i}

$2^{-i}$

@ david-richerby: Apakah tidak menyatakan kembali masalah dengan cara yang berbeda, memberikan cara yang lebih mudah untuk memikirkannya, tepatnya apa itu memberikan intuisi? Perhatikan juga bahwa Anda juga menyatakan kembali masalahnya, dari jumlah waktu hingga jumlah bilangan rasional. Langkah pendek (sangat) ya, tapi ulangan tidak kurang. Jika Anda tahu tentang konvergensi jumlah bilangan rasional, ulangan itu membuatnya lebih mudah untuk dipahami, tetapi bagi sebagian orang, saya yakin lebih mudah memahaminya dalam hal air. Setidaknya itulah bagaimana saya pertama kali memahami mengapa beberapa jumlah tak terbatas bertemu dan beberapa tidak.

epa095

@ epa095 Memberikan intuisi melibatkan menjelaskan situasi yang tidak dikenal dengan merujuk pada situasi yang sudah dikenal dan menggunakan keakraban dengan satu situasi untuk membantu memahami yang lain. Anda tidak melakukan itu: Anda mencoba menjelaskan satu situasi yang tidak dikenal (menghitung jumlah yang tak terbatas, konvergen) dengan yang lain (menuangkan ember air yang dapat dibagi tak terhingga dengan akurasi sempurna). Orang yang tahu tentang konvergensi jumlah tidak perlu analogi; untuk orang yang tidak tahu tentang konvergensi jumlah, mengganti nama "bilangan rasional" menjadi "kuantitas air hipotetis" tidak membantu.

David Richerby