Sudah waktunya untuk menghadapi kebenaran: Kita tidak akan berada di sini selamanya, tetapi setidaknya kita dapat menulis sebuah program yang akan hidup lebih lama dari umat manusia bahkan jika itu berjuang sampai akhir zaman.
Tugas Anda adalah menulis sebuah program yang memiliki waktu berjalan yang diharapkan lebih besar daripada waktu yang tersisa hingga akhir jagat raya.
Anda dapat berasumsi bahwa:
- Alam semesta akan mati karena entropi dalam 10 1000 tahun.
- Komputer Anda:
- Akan hidup lebih lama dari alam semesta, karena terbuat dari Unobtainium .
- Memiliki batas memori / stack / rekursi tak terbatas.
- Prosesornya memiliki kecepatan terbatas.
Anda harus menunjukkan bahwa program Anda berakhir (maaf, tidak ada loop tak terbatas) dan menghitung waktu berjalan yang diharapkan.
The celah standar berlaku.
Ini adalah tantangan kode golf, jadi kode terpendek yang memenuhi kriteria menang.
EDIT :
Sayangnya, ditemukan (30 menit kemudian) bahwa bidang ketidakmungkinan Unobtainium mengganggu jam internal komputer, menjadikannya tidak berguna. Jadi program berbasis waktu segera berhenti. (Lagipula, siapa yang akan meninggalkan program yang hanya menunggu warisannya?).
Prosesor komputer mirip dengan Intel i7-4578U, jadi salah satu cara untuk mengukur waktu berjalan adalah dengan menjalankan program Anda di komputer yang sama dengan input yang lebih kecil (saya harap) dan memperkirakan waktu berjalannya.
Mimbar
#CharsLanguageUpvotes Author
1 5 CJam 20 Dennis
2 5 J 5 algorithmshark
3 7 GolfScript 30 Peter Taylor
4 9 Python 39 xnor
5 10 Matlab 5 SchighSchagh
* Suara positif pada 31/08
sumber
Jawaban:
CJam, 5 byte
Bagaimana itu bekerja
Program ini akan berhenti ketika tumpukan tidak dapat menyimpan Big Integer lagi, yang tidak akan terjadi dalam waktu dekat di komputer desktop modern.
Ukuran heap default adalah 4.179.623.936 byte di komputer saya (Java 8 di Fedora). Ini dapat ditingkatkan ke nilai arbitrer dengan
-Xmx
, jadi satu-satunya batas nyata adalah memori utama yang tersedia.Waktu kematian
Dengan asumsi bahwa penerjemah membutuhkan x bit memori untuk menyimpan Big Integer non-negatif kurang dari 2 x , kita harus menghitung hingga 2 8 × 4.179.623.936 = 2 33.436.991.488 . Dengan satu peningkatan per siklus clock dan Core i7-3770 (3,9 GHz dengan turbo), ini akan membutuhkan 2 33.436.991.488 ÷ 3.400.000.000> 10 10.065.537.393 detik, yang lebih dari 10 10.065.537.385 tahun.
sumber
!=
tak terbatas tipe data tak terbatas. Jika saya memiliki satu terabyte RAM, integer 8-bit yang tidak ditandatangani masih naik hingga 255.JavaScript, 39
Penjelasan
Karena JavaScript tidak tepat mewakili bilangan bulat besar, loop
for(;x!=++x;)
berakhir setelahx
hit9007199254740992
.Tubuh for for akan dieksekusi
Fib(9007199254740992) - 1
kali, di manaFib(n)
adalah nomor fibonacci ke-n.Dari pengujian, saya tahu komputer saya akan melakukan kurang dari 150.000 iterasi per detik. Pada kenyataannya, itu akan berjalan jauh lebih lambat karena tumpukan akan tumbuh sangat besar.
Dengan demikian, program akan membutuhkan setidaknya
(Fib(9007199254740992) - 1) / 150000
detik untuk menjalankannya. Saya belum dapat menghitungFib(9007199254740992)
karena ini sangat besar, tetapi saya tahu bahwa itu jauh lebih besar dari 10 1000 * 150.000.EDIT: Seperti disebutkan dalam komentar,
Fib(9007199254740992)
sekitar 4.4092 * 10 1882393317509686 , yang memang cukup besar.sumber
fib(n)
dapat didekati denganphi^n
, kita dapat menggunakanlog((sqrt(5) + 1)/2)*9007199254740992
untuk menghitung berapa banyak digitfib(9007199254740992)
ternyata1.8823933*10^15
.Fib(9007199254740992)
(menggunakan bentuk kontinu denganphi
) kira-kira4.4092... * 10^1882393317509686
. Perhitunganfor(x=0;x!=++x;)
dan hanya mengulangi 9007199254740992 kali.Python (9)
Ini memiliki lebih dari 10 ** 10.000.000 bit, jadi menghitungnya akan membawa kita jauh melewati kematian panas.
Saya memeriksa bahwa ini membutuhkan lebih banyak waktu untuk nilai yang lebih besar tetapi masih masuk akal, jadi ini bukan hanya dioptimalkan oleh penerjemah.
Sunting: Golf dua karakter dengan menghapus parens berkat @ user2357112. TIL yang Python memperlakukan eksponen berturut-turut sebagai menara listrik.
sumber
...82528057365719799011536835265979955007740933949599830498796942400000000009
(2,6 * 10 ^ 954242509 digit dihilangkan untuk menghindari lubang hitam runtuh ). Anda harus benar-benar meningkatkan ke Unobtanium.9**9**9e9
itu sama pendeknya dan membutuhkan sedikit lebih banyak jagad raya untuk dihitung, dan juga terlihat sedikit lebih bagus.GolfScript (
127 karakter)Ini menghitung dan mencetak 8 ^ 7 ^ 6 ^ 5 ^ 4 ^ 3 ^ 2 ~ = 10 ^ 10 ^ 10 ^ 10 ^ 183230. Untuk mencetaknya (apalagi perhitungannya) dalam 10 ^ 1000 tahun ~ = 10 ^ 1007,5 detik, perlu mencetak sekitar 10 ^ (10 ^ 10 ^ 10 ^ 183230 - 10 ^ 3) digit per detik.
sumber
Marbelous
6866 byteMarbelous adalah bahasa 8 bit dengan nilai-nilai hanya diwakili oleh kelereng dalam mesin seperti Rube Goldberg, jadi ini tidak mudah. Pendekatan ini kira-kira setara dengan pseudo-code berikut:
karena nilai maksimum adalah 256, (diwakili oleh 0 dalam program Marbleous, yang ditangani secara berbeda di tempat yang berbeda) Fungsi rekursif (1) akan dipanggil dengan total
256!*512^256
yang sama dengan10^1200
, cukup mudah untuk hidup lebih lama dari alam semesta.Marbelous tidak memiliki juru bahasa yang sangat cepat, sepertinya bisa menjalankan
10^11
panggilan fungsi ini per tahun, yang berarti kita sedang melihat runtime10^1189
tahun.Penjelasan lebih lanjut dari dewan Marbelous
00
adalah bahasa literal (atau marmer), diwakili dalam heksadesimal (jadi 0). Marmer ini jatuh ke bawah--
, yang akan menurunkan marmer sebanyak 1 (00 membungkus dan berubah menjadi FF atau 255 dalam desimal). Marble dengan nilai FF jatuh ke bawah\\
yang mendorongnya satu kolom ke kanan, ke bawah@0
. Ini adalah portal dan memindahkan marmer ke@0
perangkat lain . Di sana, marmer mendarat di/\
perangkat, yang merupakan duplikator, menempatkan satu salinan marmer di sebelah--
kiri (marmer ini akan terus berputar di antara portal dan dikurangi pada setiap loop) dan satu di sebelah=0
kanan.=0
membandingkan marmer dengan nilai nol dan membiarkan marmer jatuh jika itu sama dan mendorongnya ke kanan jika tidak. Jika marmer memiliki nilai 0, ia akan mendarat di&0
, sinkronisasi, yang akan saya jelaskan lebih lanjut, nanti.Secara keseluruhan, ini hanya dimulai dengan marmer bernilai 0 dalam satu lingkaran dan menurunkannya hingga mencapai 0 lagi, lalu menempatkan marmer bernilai 0 ini dalam sinkronisasi dan terus mengulang pada waktu yang sama.
}0
adalah perangkat input, awalnya input baris perintah n (basis 0) saat memanggil program ditempatkan di setiap}n
perangkat. Jadi jika Anda memanggil program ini dengan input baris perintah 2, marmer nilai 02 akan menggantikan ini}0
. Marmer ini kemudian jatuh ke dalam&0
perangkat, sinkronisasi lain,&n
sinkronisasi memegang kelereng sampai semua korespondensi lainnya&n
diajukan juga. Marmer kemudian akan dikurangi, diteleportasi dan digandakan seperti pada loop yang dijelaskan sebelumnya. Salinan yang tepat kemudian diperiksa ketidaksetaraannya dengan nol (>0
) jika bukan 0, ia gagal. Jika 0, maka akan didorong ke kanan dan mendarat!!
, yang mengakhiri papan.Oke, sejauh ini kita memiliki loop yang terus-menerus menghitung mundur dari 255 ke 0 dan memungkinkan loop serupa lainnya (diumpankan oleh input baris perintah) berjalan sekali setiap kali klik 0. Ketika loop kedua ini telah berjalan n kali (maksimum 256) ) program berakhir. Jadi itu maksimum 65536 putaran. Hampir tidak cukup untuk hidup lebih lama dari alam semesta.
Ini harus mulai terlihat akrab, input akan dikurangi satu kali, kemudian nilai ini berputar dan disalin (perhatikan bahwa marmer hanya akan dikurangi satu kali, bukan pada setiap putaran). Kemudian akan diperiksa untuk kesetaraan ke 0 dan jika tidak nol
MB
. Ini adalah fungsi di Marbelous, setiap file dapat berisi beberapa papan dan setiap papan adalah fungsi, setiap fungsi harus dinamai dengan mendahului grid oleh:[name]
. Setiap fungsi kecuali untuk fungsi pertama dalam file, yang memiliki nama standar: MB. Jadi loop ini terus menerus memanggil papan utama lagi dengan nilai din - 1
mana n adalah nilai yang dengannya instance fungsi ini dipanggil.Jadi mengapa
n*512
?Nah, loop pertama berjalan dalam 4 tick (dan 256 kali) dan loop kedua berjalan n kali sebelum board berakhir. Ini berarti papan menjalankan sekitar
n*4*256
kutu. Loop terakhir (yang melakukan pemanggilan fungsi rekursif) adalah compacter dan berjalan dalam 2 ticks, yang berarti ia berhasil memanggil fungsin*4*256/2 = n*512
kali.Apa simbol yang tidak Anda sebutkan?
\/
adalah tempat sampah, yang menghilangkan kelereng dari papan, ini memastikan kelereng yang telah discart tidak mengganggu kelereng lain yang mengulang putaran dan mencegah program dari penghentian.Bonus
Karena kelereng yang jatuh di bagian bawah papan marbelous mendapatkan output ke STDOUT, program ini mencetak sejumlah besar karakter ASCII saat dijalankan.
sumber
Perl,
6658 karakterDi atas adalah implementasi dari fungsi Ackermann – Péter . Saya tidak tahu seberapa besar A (9,9), tetapi saya cukup yakin akan butuh waktu lama untuk mengevaluasi.
sumber
$n?A($m-1,A($m,$n-1)):A($m-1,1)
mengakui penghematan 8-char yang mudah dengan mendorong operator ternary.MATLAB,
5852 karakterKami membutuhkan setidaknya satu solusi aritmatika presisi-terbatas, karenanya:
x = yang (1.999); y = x; sedangkan sembarang (y), y = mod (y + x, bilangan prima (7910)); akhir( terima kasih kepada @DennisJaheruddin karena merobohkan 6 karakter )
Jumlah siklus yang diperlukan untuk menyelesaikan diberikan oleh produk dari 999 bilangan prima pertama. Karena sebagian besar dari ini adalah lebih dari 10, waktu yang dibutuhkan untuk mewujudkan konvergensi akan ratusan atau ribuan pesanan besarnya lebih besar dari batas waktu minimum.
sumber
p=1:9e9;y=p;while+y*y',y=mod(y+1,p),end
Mathematica,
2519 byteSolusi ini diposting sebelum fungsi waktu didiskualifikasi.
TimeUsed[]
mengembalikan detik sejak sesi dimulai, dan Mathematica menggunakan tipe presisi sewenang-wenang. Ada sekitar 10 7 detik dalam setahun, jadi menunggu 10 10.000 detik sudah cukup.Alternatif yang lebih pendek / sederhana (/ valid):
Mari kita hitung saja. Kita harus menghitung sedikit lebih jauh, karena kita dapat melakukan cukup banyak peningkatan dalam sedetik, tetapi batas yang lebih tinggi sebenarnya tidak memerlukan karakter.
Secara teknis, di kedua solusi, saya bisa menggunakan batas yang jauh lebih rendah karena masalahnya tidak menentukan kecepatan prosesor minimum.
sumber
9^9^9
membutuhkan waktu lebih dari10^1000
bertahun - tahun? Saya memperkirakan bahwa komputasi9^9^9
menggunakan 1.3GHz U7300 sayabc
akan memakan waktu kurang dari 6 bulan. (Berdasarkan9^200000
9^400000
Python 3 - 49
Ini melakukan sesuatu yang berguna: menghitung Pi hingga akurasi yang belum pernah terjadi sebelumnya menggunakan seri tak terbatas Gregory-Leibniz.
Kalau-kalau Anda bertanya-tanya, program ini berulang
10**10**10**2.004302604952323
kali.Presisi sewenang-wenang: 78
Sumber gambar
Napas Terminal
Karena perhitungan besar yang terjadi,
1e99**1e99
iterasi berlangsung di bawah1e99**1e99
tahun. Sekarang,(1e99**1e99)-1e1000
hampir tidak ada bedanya. Itu berarti bahwa program ini akan berjalan jauh lebih lama daripada kematian alam semesta kita.Kelahiran kembali
Sekarang, para ilmuwan mengusulkan bahwa di dalam
10**10**56 years
, alam semesta akan terlahir kembali karena fluktuasi kuantum atau penerowongan. Jadi, jika setiap alam semesta persis sama, berapa banyak alam semesta yang akan dijalani program saya?Dengan asumsi bahwa alam semesta akan selalu hidup
1e10+1e1000
bertahun-tahun dan kemudian butuh10**10**56
bertahun - tahun untuk 'reboot', program saya akan hidup melalui1e9701
alam semesta. Ini dengan asumsi, tentu saja, bahwa unobtainium dapat hidup melalui Big Bang.sumber
1000**1000
adalah1e3000
, tidak1e2000
.100**100=1E200
.Python 59 (bekerja sebagian besar waktu)
Saya tidak bisa menolak
Walaupun benar bahwa ini secara teoritis dapat berakhir dalam waktu kurang dari satu milidetik, runtime rata-rata adalah lebih dari
10^400
waktu umur yang ditentukan alam semesta. Terima kasih kepada @BetaDecay, @undergroundmonorail, dan @DaboRoss untuk mendapatkan 17 karakter atau lebih.sumber
continue
denganpass
J - 5 karakter, saya kira
Perhatikan bahwa semua berikut ini dalam aritmatika presisi sewenang-wenang, karena angka 9 selalu memiliki sedikit
x
di sampingnya.Dalam tujuh karakter, yang kita miliki
!^:!!9x
, yang agak seperti berlaridalam aritmatika presisi sewenang-wenang. Ini jelas melebihi batas karena Synthetica berkata demikian , jadi kami memiliki batas atas.
Dalam enam karakter, kita juga bisa menulis
^/i.9x
, yang menghitung setiap hasil antara0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8
. Wolfram | Alpha mengatakan2^3^4^5^6^7^8
kira-kira10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185
, yang mungkin juga membersihkan inspeksi.Kami juga memiliki lima karakter
!!!9x
, yaitu ((9!)!) !. W | A mengatakan itu10 ^ 10 ^ 10 ^ 6.2695
, yang seharusnya masih cukup besar ... Itu seperti1.6097e1859933
digit -ish, yang jelas lebih besar dari3.154e1016
, jumlah nanodetik di alam semesta, tapi aku akan mengakui bahwa aku tidak tahu bagaimana orang bisa mencari tahu runtimes nyata dari hal-hal ini.Pencetakan saja harus cukup lama untuk bertahan lebih lama dari alam semesta, jadi itu harus baik-baik saja.
sumber
C,
6356 karakterMembuktikan bahwa itu berakhir dilakukan dengan induksi.
Membuktikan langkah induksi dengan induksi:
sumber
Matlab (
108 karakter)IMHO, sebagian besar entri berusaha terlalu keras dengan menghitung hal-hal besar dan rumit. Kode ini hanya akan menginisialisasi array 9x10 1016
double
s yang dihitung dari 1, yang membutuhkan 7.2x10 ^ 1017 byte. Pada CPU modern dengan bandwidth memori maksimum 21 GB / s atau 6,63x10 ^ 17 byte / tahun , akan membutuhkan setidaknya 1,09x10 1000 tahun untuk menginisialisasi array, apalagi mencoba mencetaknya karena saya tidak repot-repot mencetaknya. menekan output dengan tanda titik koma. (;solusi lama
kalau tidak
Kode ini hanya akan membuat matriks kuadrat
NaN
s / infinities dengan ukuran3e508
x3e508 = 9e1016
8-byte atau7.2e1017
byte.sumber
Perl, 16 karakter
Ini membangun string yang berulang ". *" Satu miliar kali, kemudian menggunakannya sebagai jarum dan tumpukan jerami dalam pertandingan regex. Ini, pada gilirannya, menyebabkan mesin regex mencoba setiap partisi yang mungkin dari string yang panjangnya dua miliar karakter. Menurut rumus dari Wikipedia ini , ada sekitar 10 35.218 partisi seperti itu.
Solusi di atas adalah 16 karakter, tetapi hanya membutuhkan sekitar 2Gb memori, yang berarti dapat dijalankan pada komputer nyata. Jika kita mengasumsikan memori tak terbatas dan ukuran register terbatas (yang mungkin tidak masuk akal), itu dapat dipersingkat menjadi 15 karakter sekaligus secara dramatis meningkatkan runtime:
(Saya belum mengujinya, tapi saya pikir itu bisa bekerja dengan Perl 32-bit yang dibangun pada mesin 64-bit dengan setidaknya 6Gb RAM.)
Catatan:
x
adalah operator pengulangan string.for
bukan merupakan lingkaran yang sebenarnya; hanya digunakan untuk menyimpan satu karakter (dibandingkan dengan$_=".*"x1e9;/$_^/
).^
di regex memastikan bahwa hanya string kosong yang bisa cocok; karena regex quantifiers serakah secara default, ini adalah hal terakhir yang akan dicoba oleh mesin.sumber
J (12)
Apa ini turun ke dalam Python (dengan asumsi
!
bekerja):SUNTING:
Nah, program ini dapat, paling banyak,
2 × 10^-1858926
detik per siklus, untuk menyelesaikan dalam waktu yang diperlukan. Kiat: ini bahkan tidak akan bekerja untuk siklus pertama, apalagi yang terakhir;).Juga: program ini mungkin membutuhkan lebih banyak memori daripada ada entropi di alam semesta ...
sumber
xrange()
;)!
tidak berfungsi dengan Python. Anda membutuhkanimport math
danmath.factorial()
.C # 217
Saya tidak banyak pegolf, tapi saya tidak bisa menahan fungsi Ackerman . Saya juga tidak benar-benar tahu cara menghitung runtime, tetapi pasti akan berhenti, dan pasti akan berjalan lebih lama dari versi ini .
sumber
ack
fungsi menjadi nama karakter tunggal sepertia
.Usaha pertama di kode golf tapi begini.
VBA -
5745Jadi X akan naik satu jika kejadian 1 in 2 ^ 128 terjadi dan reset jika itu tidak terjadi. Kode berakhir ketika peristiwa ini terjadi 2 ^ 64 + 1 kali berturut-turut. Saya tidak tahu bagaimana cara mulai menghitung waktu, tetapi saya rasa ini sangat besar.
EDIT: Saya menghitung matematika dan kemungkinan ini terjadi di setiap loop adalah 1 dalam 2 ^ 128 ^ (1 + 2 ^ 64) yang panjangnya sekitar 20.000 digit. Dengan asumsi 10.00000 loop / detik (rata-rata dari jumlah udara tipis) dan 30000000 s / tahun itu 3 * 10 ^ 13 siklus per tahun waktu 10 ^ 1000 tahun tersisa adalah 3 * 10 ^ 1013 siklus, jadi ini kemungkinan akan bertahan sekitar 20 kali lipat sisa waktu tersisa di alam semesta. Saya senang matematika saya mendukung intuisi saya.
sumber
While x=1
, bukan? (Jika tidak, ini merupakan loop tak terbatas). Anda juga dapat mencukur habis 12 chars jika Anda menggantiDim x As Double
denganx=0
(VBA tidak perlu mendeklarasikan variabel kecuali jika Anda menentukanOption Explicit
)C, 30 karakter
Dengan asumsi pujian dua ditandatangani meluap dan int 32-bit, ini akan berjalan selama 2 2 32 panggilan fungsi, yang seharusnya menjadi banyak waktu bagi alam semesta untuk berakhir.
sumber
GolfScript, 13 karakter
Program ini hanya menghitung dari 0 hingga 10 9 9 −1 = 10 387420488 . Dengan asumsi, secara optimis, bahwa komputer berjalan pada 100 GHz dan dapat menjalankan setiap iterasi program dalam satu siklus, program akan berjalan selama 10 9 9 −12 detik, atau sekitar 3 × 10 9 9 −20 = 3 × 10 387420469 tahun.
Untuk menguji program, Anda dapat mengganti
9
dengan2
, yang akan membuatnya berhenti di 10 2 2 −1 = 10 3 = 1000. (Menggunakan3
bukannya2
akan membuatnya berhenti di 10 3 3 −1 = 10 26 , yang , bahkan dengan asumsi optimis di atas, itu tidak akan mencapai setidaknya beberapa juta tahun.)sumber
Autohotkey 37
sumber
Haskell, 23
Program ini berakhir setelah membaca 1073741824 karakter dari
stdin
. Jika dijalankan tanpa memipipkan data apa punstdin
, Anda harus mengetikkan jumlah karakter ini di keyboard Anda. Dengan asumsi keyboard Anda memiliki 105 tombol, masing-masing diperingkat untuk siklus mekanik 100k dan diprogram untuk menghasilkan penekanan tombol yang tidak mati, autorepeat tidak aktif, dan soket keyboard Anda memungkinkan 100 siklus koneksi, ini memberikan jumlah maksimum penekanan tombol per komputer waktu aktif 1050000000, yang merupakan tidak cukup untuk menghentikan program.Oleh karena itu, program hanya akan berakhir ketika perangkat keras yang lebih baik tersedia dalam hal jumlah siklus, yang secara efektif tidak pernah ada di dunia yang sedang berjalan ini. Mungkin lain kali, ketika kualitas memiliki prioritas lebih tinggi daripada kuantitas. Sampai saat itu, program ini berakhir pada prinsipnya tetapi tidak dalam praktiknya.
sumber
~ ATH, 56
Dalam bahasa fiksi ~ ATH :
Saya minta maaf atas pelanggaran celah perbatasan; Saya pikir itu terlalu relevan untuk dilewatkan.
Jika ada yang benar-benar terhibur dengan ini, lebih detail: (1) , (2) , (3) , (4)
sumber
Ruby (34)
Jalur ini
([0]*9).permutation.each{print}
membutuhkan waktu sekitar 2,47 detik selama 9! mencetak pada mesin saya, sementara garis([0]*10).permutation.each{print}
membutuhkan sekitar 24,7 detik selama 10! cetakan, jadi saya kira saya bisa memperkirakan di sini dan menghitung(24.7/10!)*470! seconds in years
yang 6,87 * 10 ^ 1040, yang seharusnya menjadi jangka waktu:sumber
JavaScript
6862 karakterIni menggunakan fungsi Ackermann yang dapat ditulis sebagai
Waktu runtime-nya meningkat secara eksponensial dan karenanya sangat lama untuk dihitung. Meskipun ini bukan bahasa Inggris di sini Anda bisa mendapatkan gambaran tentang nilai pengembaliannya. Menurut tabel
ackermann(5,1)
sama dengan2↑↑(65533)-3
yang, Anda tahu, sangat besar.sumber
n==0?X:Y
, Anda selalu dapat melakukannyan?Y:X
Befunge '93 - 40 byte
(Program 20x2)
Program ini bergantung pada angka acak untuk memberikan penundaan. Karena juru bahasa Befunge sangat lambat, program ini harus sesuai dengan tagihan. Dan jika tidak, kita selalu dapat mengembangkannya secara horizontal. Saya tidak yakin bagaimana cara menghitung waktu berjalan yang diharapkan dari program ini, tapi saya tahu masing-masing? memiliki peluang 50/50 untuk memulai kembali atau mengubah posisi horisontal dengan 1. Ada 18? Saya pikir itu harus menjadi sesuatu di sepanjang baris (18 ^ 2) !, yang menurut kalkulator Google adalah "Infinity"
EDIT: Whoops saya tidak melihat jawaban Befunge lainnya, ini adalah posting pertama saya di sini. Maaf.
sumber
APL, 10
Saya tidak berpikir ini adalah jawaban yang valid (karena tidak menentukan), tetapi bagaimanapun juga ......
Program ini menghitung permutasi acak nomor 1e9 (
?⍨1e9
) dan mengulangi sampai dua output berturut-turut sama (⍣≡
)Jadi, setiap kali permutasi dihitung, ia memiliki 1 dalam 1000000000! kesempatan untuk mengakhiri. Dan 1000000000! setidaknya 10 10 8 .
Waktu yang diperlukan untuk menghitung permutasi diberikan tidak relevan oleh besarnya 1000000000 !. Tetapi beberapa pengujian menunjukkan ini
O(n)
dan ekstrapolasi memberi sekitar 30 detik.Namun, juru bahasa saya menolak untuk mengambil input ke fungsi acak yang lebih besar dari 2 31 -1 (jadi saya menggunakan 1e9), dan menghasilkan permutasi angka 1000000000 memberi ruang kerja kesalahan penuh. Namun, secara konseptual dapat dilakukan dengan juru APL yang ideal dengan memori tak terbatas.
Ini membawa kita pada kemungkinan menggunakan 2 63 -1 sebagai pengganti 1e9 untuk meningkatkan waktu berjalan hingga setidaknya 10 10 20 , dengan asumsi arsitektur 64-bit.
Tapi tunggu, apakah arsitektur relevan dengan penerjemah ideal? Persetan tidak, jadi sebenarnya tidak ada batas waktu berlari !!
sumber
R, 45 byte
Itu adalah utas lama tapi saya tidak melihat jawaban R, dan kita tidak mungkin memilikinya!
Runtime untuk saya adalah sekitar 1s ketika x adalah 20, menunjukkan runtime 2 ^ 9979 detik.
Jika Anda mengganti nol dengan yang satu, maka output akan menjadi 2 ^ x, tetapi seperti berdiri output adalah nol apa pun x itu (menghindari masalah melimpah).
sumber
Javascript, 120 byte
Dapat dilakukan dengan memori minimal (mungkin kurang dari setengah megabyte) tetapi membutuhkan (mungkin) sekitar 10.850 tahun untuk berhenti.
Berulang kali menambah basis big-endian -9 BigInteger-9 hingga mencapai 9 10 4 -1 .
sumber
Python 3, 191 Bytes
Pertama, f adalah fungsi faktorial rekursif dan sangat lambat. Lalu, ada 9 * 10⁹⁹⁹ yang dibajak dengan sendirinya, yang menghasilkan OverflowError, tetapi ini tidak terjadi pada komputer Unobtanium ini. For-Loop mengulangi 9E999! ^ (9E999 ^ 9E999)! kali dan itu hanya menuju ke iterasi berikutnya, jika 9E999! +1 int acak antara 0 dan 9E99 * ^ i! semua 0 dan di setiap iterasi dari while-loop diatur ke (9E999 ^ s) !. Eh, saya lupa bahwa pencetakan s membutuhkan waktu muuuuccchhhh ...
Saya tahu itu bukan solusi terpendek, tapi saya pikir itu benar-benar efektif. Dapatkah seseorang membantu saya menghitung waktu berjalan?
sumber
Turing Machine But Way Worse , 167 byte
Cobalah online!
Harus menjalankan 6-negara 2 simbol 2 Sibuk Berang-berang dari halaman Wikipedia .
sumber