Jika suatu program berakhir dan tidak ada yang melihatnya, apakah itu berhenti?

99

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

kb_sou
sumber
40
Saya tergoda untuk membuat tag [kode paling lambat] untuk pertanyaan ini. : P
Doorknob
5
Bogosort tidak akan berfungsi karena walaupun tidak mungkin tidak akan pernah selesai, mungkin memerlukan waktu yang tidak terbatas untuk menyelesaikannya. Namun, ada banyak ekspresi reguler berbasis-NFA yang mengerikan yang dapat memenuhi kriteria "akan selesai, tetapi tidak sebelum alam semesta mati".
DavidO
49
Judul Anda harus berupa kaos
user-2147482637
4
Pertanyaan yang bagus, tetapi bukankah itu seharusnya kontes popularitas?
IazertyuiopI
12
Saya pikir Isaac Asimov menulis cerita tentang ini .
David Conrad

Jawaban:

34

CJam, 5 byte

0{)}h

Bagaimana itu bekerja

 0   " Push 0.                                 ";
 {   "                                         ";
   ) " Increment the Big Integer on the stack. ";
 }h  " Repeat if the value is non-zero.        ";

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.

Dennis
sumber
14
Saya tidak berpikir Anda dapat mengandalkan sumber daya yang terbatas, karena pertanyaannya menyatakan "Komputer Anda memiliki batas memori / stack / rekursi tak terbatas".
Greg Hewgill
4
Memori !=tak terbatas tipe data tak terbatas. Jika saya memiliki satu terabyte RAM, integer 8-bit yang tidak ditandatangani masih naik hingga 255.
wchargin
6
@GregHewgill: Dengan sumber daya tidak terbatas, Anda dapat meningkatkan ukuran heap Java maksimum ke nilai sembarang, tetapi akan selalu terbatas.
Dennis
2
@ Dennis, tapi kemudian tambahkan saja setiap kali melalui loop untuk menggandakan ukuran tumpukan. Ini hal yang lucu tentang infinities :-)
Carl Witthoft
9
@CarlWitthoft: Anda tidak dapat melakukannya dari dalam program.
Dennis
62

JavaScript, 39

(function f(x){for(;x!=++x;)f(x+1)})(0)

Penjelasan

Karena JavaScript tidak tepat mewakili bilangan bulat besar, loop for(;x!=++x;)berakhir setelah xhit 9007199254740992.

Tubuh for for akan dieksekusi Fib(9007199254740992) - 1kali, di mana Fib(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) / 150000detik untuk menjalankannya. Saya belum dapat menghitung Fib(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.

Peter Olson
sumber
9
Karena fib(n)dapat didekati dengan phi^n, kita dapat menggunakan log((sqrt(5) + 1)/2)*9007199254740992untuk menghitung berapa banyak digit fib(9007199254740992)ternyata 1.8823933*10^15.
overactor
11
@overactor, Menurut Wolfram Alpha, Fib(9007199254740992)(menggunakan bentuk kontinu dengan phi) kira-kira 4.4092... * 10^1882393317509686. Perhitungan
Brian S
1
tumpukan yang bertambah tidak mengurangi kecepatan CPU ... kecuali jika Anda mempertimbangkan lebar jalur alamat memori terbatas / lebar alamat tidak terbatas (dalam hal ini perlambatan masih linier dalam panjang alamat dengan asumsi penyandian yang masuk akal) atau bahkan keterbatasan fisik dalam penyimpanan memori dan kecepatan cahaya (dalam hal ini perlambatan adalah nilai alamat yang diasumsikan sebagai penyimpanan spasial; bahkan tingkat kepadatan data DNA akhirnya mulai bertambah, bahkan jika Anda mengelola akses acak hemat-ruang)
John Dvorak
1
@JamesKhoury Tidak, fungsi yang baru saja Anda tulis setara dengan for(x=0;x!=++x;)dan hanya mengulangi 9007199254740992 kali.
Peter Olson
4
@ SilvainLeroux sebuah arsitektur dengan jumlah RAM yang tak terbatas mungkin hanya akan menumpuk tumpukan dan tumpukan dan membuat keduanya tumbuh ke atas.
John Dvorak
47

Python (9)

9**9**1e9

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.

Tidak
sumber
4
OverflowError: (34, 'Hasil terlalu besar')
apple16
93
@ apple16 Mungkin di komputer Anda, tetapi milik saya memiliki "batas memori / tumpukan / rekursi tak terbatas".
xnor
64
Tidak apa-apa, kawan. Saya menjalankannya alam semesta terakhir dan mendapatkan ...82528057365719799011536835265979955007740933949599830498796942400000000009(2,6 * 10 ^ 954242509 digit dihilangkan untuk menghindari lubang hitam runtuh ). Anda harus benar-benar meningkatkan ke Unobtanium.
xnor
10
Eksponensial adalah asosiatif yang benar, sehingga Anda dapat melepaskan tanda kurung.
user2357112
10
Perlu dicatat bahwa 9**9**9e9itu sama pendeknya dan membutuhkan sedikit lebih banyak jagad raya untuk dihitung, dan juga terlihat sedikit lebih bagus.
abarnert
35

GolfScript ( 12 7 karakter)

9,{\?}*

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.

Peter Taylor
sumber
22
Tapi itu akan berhenti jauh sebelum itu dengan pesan "printer dari kertas" ...
Floris
1
@ Floris siapa sih yang menggunakan media fisik belakangan ini?
John Dvorak
3
@JanDvorak, saya hanya berasumsi bahwa Floris dan 7 orang yang membesarkannya berasal dari generasi kakek saya, ketika semua output adalah kertas umpan terus menerus.
Peter Taylor
2
@PeterTaylor - mungkin tidak cukup yang lama, tapi saya saya cukup tua untuk mengingat mengirimkan "pekerjaan batch" untuk "komputer" (pada hari-hari ketika ada tidak diragukan lagi, dalam populasi siswa 20k, yang komputer Anda berarti), dan mengumpulkan hasil cetak pada hari berikutnya. Anda (dan 7 lainnya) dengan tepat menduga bahwa ini adalah upaya humor, bukan kritik serius terhadap naskah Anda yang sangat bagus dan sangat pendek.
Floris
35

Marbelous 68 66 byte

}0
--@2
@2/\=0MB
}0@1\/
&0/\>0!!
--
@1
00@0
--/\=0
\\@0&0

Marbelous 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:

function recursiveFunction(int i)
{
    for(int j = i*512; j > 0; j--)
    {
        recursiveFunction(i - 1);
    }
}

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^256yang sama dengan 10^1200, cukup mudah untuk hidup lebih lama dari alam semesta.

Marbelous tidak memiliki juru bahasa yang sangat cepat, sepertinya bisa menjalankan 10^11panggilan fungsi ini per tahun, yang berarti kita sedang melihat runtime 10^1189tahun.

Penjelasan lebih lanjut dari dewan Marbelous

00@0
--/\=0
\\@0&0

00adalah 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 @0perangkat 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 =0kanan.=0membandingkan 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@1
&0/\>0!!
--
@1

}0adalah perangkat input, awalnya input baris perintah n (basis 0) saat memanggil program ditempatkan di setiap }nperangkat. Jadi jika Anda memanggil program ini dengan input baris perintah 2, marmer nilai 02 akan menggantikan ini }0. Marmer ini kemudian jatuh ke dalam &0perangkat, sinkronisasi lain, &nsinkronisasi memegang kelereng sampai semua korespondensi lainnya &ndiajukan 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.

}0
--@2
@2/\=0MB

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 di n - 1mana 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*256kutu. Loop terakhir (yang melakukan pemanggilan fungsi rekursif) adalah compacter dan berjalan dalam 2 ticks, yang berarti ia berhasil memanggil fungsi n*4*256/2 = n*512kali.

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.

overactor
sumber
2
Penjelasan yang bagus, terima kasih!
Beta Decay
2
Wow, ini ide yang brilian! Bahasa Marbelous sangat menyenangkan!
rubik
2
+1 Hanya apa yang ingin saya lihat. Bahasa yang lebih gila dari BrainFuck :) Apakah ada situs web dengan tutorial dan lebih banyak info tentang itu? (Tautan judul tampaknya memiliki lebih sedikit dokumen daripada jawaban Anda)
Sylwester
2
@Sylwester, saya senang Anda menyukainya, Marbelous saat ini masih dalam pengembangan tetapi kami berharap untuk memilikinya dalam kondisi yang lebih stabil dalam waktu dekat, di mana tutorial titik, dokumentasi yang lebih luas, perpustakaan standar dan mudah-mudahan penerjemah online akan mengikuti.
overactor
21

Perl, 66 58 karakter

sub A{($m,$n)=@_;$m?A($m-1,$n?A($m,$n-1):1):$n+1;}A(9,9);

Di 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.

Greg Hewgill
sumber
5
+1 ... Saya mencoba menemukan bahasa dengan fungsi Ackermann bawaan, tetapi gagal melakukannya sebelum kesabaran saya habis. : D
Martin Ender
3
$n?A($m-1,A($m,$n-1)):A($m-1,1)mengakui penghematan 8-char yang mudah dengan mendorong operator ternary.
Peter Taylor
3
Saya cukup yakin jumlah digit dalam A (9,9) lebih besar dari volume alam semesta yang teramati yang diukur dalam panjang Planck kubik.
kasperd
6
@kasperd Itu pernyataan yang cukup besar. Volume alam semesta yang dapat diamati hanya berurutan 10 ^ 184 volume planck. Sebagai perbandingan, ada sekitar 10 ^ 19700 digit dalam angka yang menggambarkan jumlah digit dalam A (4,4), yang pada gilirannya sangat kecil dibandingkan dengan A (9,9).
user19057
3
@ user19057 Kedengarannya seperti menyebut klaim Kasperd sebagai "pernyataan besar-besaran" adalah pernyataan besar-besaran. : P
Nicu Stiurca
20

MATLAB, 58 52 karakter

Kami membutuhkan setidaknya satu solusi aritmatika presisi-terbatas, karenanya:

y=ones(1,999);while y*y',y=mod(y+1,primes(7910));end

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.

COTO
sumber
+1 Butuh beberapa saat bagi saya untuk melihat apa yang Anda lakukan di sana. Bagus!
Fixed Point
+1 CRT, bukan?
flawr
Bagus, saya pikir beberapa karakter dapat diselamatkan seperti: y = yang (1.999); sementara y * y ', y = mod (y + 1, primes (7910)); end
Dennis Jaheruddin
@DennisJaheruddin: Pemendekan yang brilian. Saya akan memperbarui.
COTO
Meskipun ini bukan solusi yang sama lagi, ini masih harus cukup mirip, dan sekali lagi sedikit lebih pendek:p=1:9e9;y=p;while+y*y',y=mod(y+1,p),end
Dennis Jaheruddin
19

Mathematica, 25 19 byte

Solusi ini diposting sebelum fungsi waktu didiskualifikasi.

While[TimeUsed[]<10^10^5]

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):

For[i=0,++i<9^9^9,]

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.

Martin Ender
sumber
Suka! Jawaban ini membuat saya benar-benar tertawa terbahak-bahak dengan senyum lebar di wajah saya.
Todd Lehman
1
Maaf, demi kreativitas, saya harus menghentikan solusi berbasis waktu (seperti yang pertama Anda). Tolong jangan membenciku. :)
kb_sou
5
@ kbsou Yah, saya sudah mengalahkannya dengan yang lain, jadi saya tidak terlalu peduli. Tetapi sebaliknya mendiskualifikasi jawaban secara retrospektif untuk perubahan aturan tidak keren. ;)
Martin Ender
1
Apakah Mathematica sangat lambat, sehingga komputasi 9^9^9membutuhkan waktu lebih dari 10^1000bertahun - tahun? Saya memperkirakan bahwa komputasi 9^9^9menggunakan 1.3GHz U7300 saya bcakan memakan waktu kurang dari 6 bulan. (Berdasarkan 9^2000009^400000
perkiraan
2
@ArtOfCode Mathematica menggunakan tipe presisi arbitrer sehingga benar-benar akan mencoba untuk menentukan nilai yang benar.
Martin Ender
16

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.004302604952323kali.

sum([4/(i*2+1)*-1**i for i in range(1e99**1e99)])

Presisi sewenang-wenang: 78

from decimal import*
sum([Decimal(4/(i*2+1)*-1**i)for i in range(1e99**1e99)])

Sumber gambar

Napas Terminal

Karena perhitungan besar yang terjadi, 1e99**1e99iterasi berlangsung di bawah 1e99**1e99tahun. Sekarang, (1e99**1e99)-1e1000hampir 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?

(1e99**1e99)/(1e10+1e1000+10**10**56)=1e9701

Dengan asumsi bahwa alam semesta akan selalu hidup 1e10+1e1000bertahun-tahun dan kemudian butuh 10**10**56bertahun - tahun untuk 'reboot', program saya akan hidup melalui 1e9701alam semesta. Ini dengan asumsi, tentu saja, bahwa unobtainium dapat hidup melalui Big Bang.

Peluruhan Beta
sumber
3
itu berakhir setelah mencapai akhir kisaran @ Pilip. ya itu berakhir, akhirnya.
Maleakhi
1
1000**1000adalah 1e3000, tidak 1e2000.
Cornstalks
1
@Cornstalks Terima kasih, saya tidak punya kalkulator yang cukup bagus untuk menemukannya, jadi saya membuat tebakan berdasarkan fakta itu 100**100=1E200.
Beta Decay
1
@ BetaDecay: Saya mungkin menyarankan Wolfram | Alpha sebagai kalkulator online . Jika Anda belum pernah menggunakannya, itu cukup luar biasa!
Cornstalks
2
@setiap orang tertarik atau 1000 ^ 1000 = (10 ^ 3) ^ 1000 = (10 * 10 * 10) * (10 * 10 * 10) * ... * (10 * 10 * 10) [1000 kali] = 10 ^ 3000
IazertyuiopI
12

Python 59 (bekerja sebagian besar waktu)

Saya tidak bisa menolak

from random import*
while sum(random()for i in range(99)):0

Walaupun benar bahwa ini secara teoritis dapat berakhir dalam waktu kurang dari satu milidetik, runtime rata-rata adalah lebih dari 10^400waktu umur yang ditentukan alam semesta. Terima kasih kepada @BetaDecay, @undergroundmonorail, dan @DaboRoss untuk mendapatkan 17 karakter atau lebih.

KSab
sumber
Untuk turun ke 71, Anda dapat menggantinya continuedenganpass
Beta Decay
@BetaDecay Tangkapan bagus
KSab
3
Saya pikir karena pertanyaannya menanyakan waktu berjalan yang diharapkan , bukan masalah bahwa ini mungkin berakhir lebih awal. Masalah yang lebih besar adalah bahwa hal itu tidak dapat dibuktikan untuk berakhir sama sekali.
user19057
4
@ user19057 Dengan asumsi apa yang dikatakan KSab, waktu berjalan yang diharapkan adalah terbatas dan program berakhir dengan probabilitas 100%. Tentu saja modul acak benar-benar menggunakan PRNG, yang bersifat siklik, jadi kemungkinan besar ini tidak akan pernah berakhir.
Jerome Baum
1
Saya pikir Anda dapat memotong 3 karakter dengan mengganti 'lulus' dengan '0'.
daboross
8

J - 5 karakter, saya kira

Perhatikan bahwa semua berikut ini dalam aritmatika presisi sewenang-wenang, karena angka 9 selalu memiliki sedikit xdi sampingnya.

Dalam tujuh karakter, yang kita miliki !^:!!9x, yang agak seperti berlari

n = 9!
for i in range(n!):
    n = n!

dalam 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 antara 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8. Wolfram | Alpha mengatakan 2^3^4^5^6^7^8kira-kira 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 6.65185, yang mungkin juga membersihkan inspeksi.

Kami juga memiliki lima karakter !!!9x, yaitu ((9!)!) !. W | A mengatakan itu 10 ^ 10 ^ 10 ^ 6.2695, yang seharusnya masih cukup besar ... Itu seperti 1.6097e1859933digit -ish, yang jelas lebih besar dari 3.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.

algoritme hiu
sumber
7

C, 63 56 karakter

f(x,y){return x?f(x-1,y?f(x,y-1):1):y+1;}main(){f(9,9);}

Ini didasarkan pada ide oleh seorang pria bernama Wilhelm. Satu-satunya kontribusi saya adalah mengkondensasi kode ke bagian pendek (dan tidak dapat dibaca) ini.

Membuktikan bahwa itu berakhir dilakukan dengan induksi.

  • Jika x adalah 0, itu akan segera berakhir.
  • Jika berakhir untuk x-1 dan y, itu juga berakhir untuk x, ini sendiri dapat ditunjukkan dengan induksi.

Membuktikan langkah induksi dengan induksi:

  • Jika y adalah 0, maka hanya ada satu panggilan rekursif dengan x-1, yang diakhiri dengan asumsi induksi.
  • Jika f (x, y-1) berakhir maka f (x, y) juga berakhir karena panggilan terdalam f adalah tepat f (x, y-1) dan panggilan terluar berakhir sesuai dengan hipotesis induksi.

Waktu berjalan yang diharapkan adalah A (9,9) / 11837 detik. Jumlah ini memiliki lebih banyak digit daripada jumlah quark di alam semesta yang dapat diamati.

kasperd
sumber
(Ab) gunakan preprocessor dan tentukan m = main, r = return, dan z = 99999, kemudian tulis ulang program Anda sebagai, f (x, y) {rx? F (x-1, y? F (x, y- 1): 1): y + 1;} m () {f (z, z);} yang akan memakan waktu sangat lama :-)
ChuckCottrill
5
@ChuckCottrill Jika aturan memperbolehkan program, yang membutuhkan makro preprocessor tertentu, dan yang tidak diperhitungkan dalam panjang program, maka tugas apa pun dapat diselesaikan dalam satu karakter.
kasperd
6

Matlab ( 10 8 karakter)

1:9e1016

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

nan(3e508)

kalau tidak

inf(3e508)

Kode ini hanya akan membuat matriks kuadrat NaNs / infinities dengan ukuran 3e508x 3e508 = 9e10168-byte atau 7.2e1017byte.

Nicu Stiurca
sumber
1
Apa itu? 1016? Itu pasti 9999! (Atau apakah saya salah paham akan sesuatu?)
Mega Man
@MegaMan Prompt masalah meminta batas bawah runtime 10 ^ 1000 tahun. Karena golf ini, saya tidak ingin menjadi boros dan menghitung terlalu lama dari itu, jadi saya mencoba menghentikannya segera setelah mencapai ambang batas mungkin. :)
Nicu Stiurca
ah, ok, tidak tahu aturan ini
Mega Man
5

Perl, 16 karakter

/$_^/for'.*'x1e9

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:

/$_^/for'.*'x~0

(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.
  • yang forbukan merupakan lingkaran yang sebenarnya; hanya digunakan untuk menyimpan satu karakter (dibandingkan dengan $_=".*"x1e9;/$_^/).
  • final ^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.
  • tolok ukur pada komputer saya untuk nilai-nilai (1..13) menunjukkan bahwa waktu berjalan sebenarnya O (exp (n)), yang bahkan lebih dari O (exp (sqrt (n))) dalam rumus Wikipedia.
Kotor
sumber
4

J (12)

(!^:(!!9))9x

Apa ini turun ke dalam Python (dengan asumsi !bekerja):

a = 9 
for i in range((9!)!):
    a = a!

SUNTING:

Nah, program ini dapat, paling banyak, 2 × 10^-1858926detik 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 ...

ɐɔıʇǝɥʇu
sumber
3
"Mungkin membutuhkan lebih banyak memori daripada entropi di alam semesta" - Anda dapat mengurangi itu dengan xrange();)
Stefan Majewsky
1
Juga, !tidak berfungsi dengan Python. Anda membutuhkan import mathdan math.factorial().
daviewales
4

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 .

class P{
static void Main(){for(int i=0;i<100;i++){for(int j=0;j<100;j++){Console.WriteLine(ack(i,j));}}}
static int ack(int m,int n){if (m==0) return n+1;if (n ==0) return ack(m-1,1);return ack(m-1,ack(m,n-1));}
}
Bebek karet
sumber
Anda dapat menyimpan 10 byte dengan mengubah nama ackfungsi menjadi nama karakter tunggal seperti a.
pppery
4

Usaha pertama di kode golf tapi begini.

VBA - 57 45

x=0
do
if rnd()*rnd()<>0 then x=0
x=x+1
while 1=1

Jadi 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.

Myles Horne
sumber
Saya pikir baris terakhir seharusnya While x=1, bukan? (Jika tidak, ini merupakan loop tak terbatas). Anda juga dapat mencukur habis 12 chars jika Anda mengganti Dim x As Doubledengan x=0(VBA tidak perlu mendeklarasikan variabel kecuali jika Anda menentukan Option Explicit)
kb_sou
Saya tidak melihatnya sebagai infinite loop karena rusak ketika x meluap yang akhirnya.
Myles Horne
Ini pasti tidak bekerja dengan sementara x = 1 karena ini biasanya akan mencegah loop berjalan.
Myles Horne
Jika melanggar dengan cara ini loop tidak memenuhi kriteria "no infinite loop", WHILE 1 = 1 dapat berubah menjadi WHILE ISNUMERIC (X).
Myles Horne
4

C, 30 karakter

main(i){++i&&main(i)+main(i);}

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.

Uristqwerty
sumber
Anda akan kehabisan tumpukan jauh sebelum itu, meskipun.
Sparr
1
@Sparr Salah satu aturannya adalah mengasumsikan ukuran tumpukan dan tumpukan tidak terbatas.
scragar
3

GolfScript, 13 karakter

0{).`,9.?<}do

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 9dengan 2, yang akan membuatnya berhenti di 10 2 2 −1 = 10 3 = 1000. (Menggunakan 3bukannya 2akan membuatnya berhenti di 10 3 3 −1 = 10 26 , yang , bahkan dengan asumsi optimis di atas, itu tidak akan mencapai setidaknya beberapa juta tahun.)

Ilmari Karonen
sumber
3

Autohotkey 37

loop {
if (x+=1)>10^100000000
break
}
Person93
sumber
3

Haskell, 23

main=interact$take$2^30

Program ini berakhir setelah membaca 1073741824 karakter dari stdin. Jika dijalankan tanpa memipipkan data apa pun stdin, 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.

TheSpanishInquisition
sumber
Bagaimana jika Anda menukar keyboard saat bepergian?
Thomas
Itu tercakup oleh 100 siklus koneksi soket keyboard.
TheSpanishInquisition
Tetapi inti masalahnya adalah bahwa program tersebut berakhir, di suatu tempat setelah kematian panas alam semesta. Program ini tidak mungkin berakhir; sekali entropi menjadi cukup tinggi, Anda tidak akan pernah memiliki keyboard lain untuk dihubungkan.
abarnert
1
Saya masih belum yakin. Jika Anda menjalankan program dari jarak jauh (atau dalam VM), maka Anda tidak dibatasi oleh kemampuan perangkat keras dari satu komputer, dan 1 miliar stroke sebenarnya tidak banyak. Selain itu, masalahnya mengatakan komputer terbuat dari unobtainium, dan keyboard juga harus, karenanya, dapat menangani 2 ^ 30 penekanan tombol ...
Thomas
3

~ ATH, 56

Dalam bahasa fiksi ~ ATH :

import universe U;
~ATH(U) {
} EXECUTE(NULL);
THIS.DIE()

~ ATH adalah bahasa yang tidak tertahankan untuk digunakan Logikanya terdiri dari apa-apa kecuali loop tak terbatas, atau paling tidak, loop konstruksi efektif yang tak berkesudahan.

Apa yang banyak ~ ATH coders lakukan adalah mengimpor konstruksi hingga dan mengikat loop ke umur mereka. Misalnya loop utama di sini akan berakhir pada kematian alam semesta, berlabel U. Dengan begitu Anda hanya perlu menunggu miliaran tahun untuk berakhir bukan selamanya.

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)

DBN
sumber
2

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 yearsyang 6,87 * 10 ^ 1040, yang seharusnya menjadi jangka waktu:

([0]*470).permutation.each{print}
Boris
sumber
2

JavaScript 68 62 karakter

(function a(m,n){return m==0?n+1:a(m-1,n==0?1:a(m,n-1))})(5,1)

Ini menggunakan fungsi Ackermann yang dapat ditulis sebagai

function ackermann(a, b) {
  if (a == 0) return b + 1;
  if (b == 0) return ackermann(a-1, 1);
  else return ackermann(a-1, ackermann(a, b-1));
}

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 dengan 2↑↑(65533)-3yang, Anda tahu, sangat besar.

henje
sumber
2
Ini dapat mengambil manfaat dari beberapa optimisasi yang sama seperti implementasi fungsi Perl Ackermann sebelumnya.
Peter Taylor
Saya pasti telah mengabaikan solusi perl. Terima kasih telah menunjukkannya.
henje
alih-alih n==0?X:Y, Anda selalu dapat melakukannyan?Y:X
Cyoce
2

Befunge '93 - 40 byte

(Program 20x2)

v<<<<<<<<<<<<<<<<<<<
>??????????????????@

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.

rodolphito
sumber
Hei, jangan khawatir tentang jawaban befubnge lainnya, atau, atau secara umum, menggunakan bahasa yang sama dengan orang lain. Maksudku, tidak ada yang akan mengalahkan yang mathlab, jadi semua kiriman lainnya adalah tentang kesenangan. Milik saya.
AndoDaan
2

APL, 10

Saya tidak berpikir ini adalah jawaban yang valid (karena tidak menentukan), tetapi bagaimanapun juga ......

{?⍨1e9}⍣≡1

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 !!

TwiNight
sumber
2

R, 45 byte

(f=function(x)if(x)f(x-1)+f(x-1)else 0)(9999)

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).

JDL
sumber
1

Javascript, 120 byte

a=[0];while(a.length<1e4)(function(){var b=0;while(b<a.length){a[b]=(a[b]+1)%9;if(a[b])return;b++}a.push(1)})();alert(a)

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 .

SuperJedi224
sumber
1

Python 3, 191 Bytes

from random import*
r=randint
f=lambda n:2if n<2else f(n-1)
x=9E999
s=x**x
for i in range(f(x)**f(s)):
 while exec(("r(0,f(x**i))+"*int(f(x)))+"r(0,f(x**i))")!=0:
  s=f(x**s)
  print(s)

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?

Mega Man
sumber
1

Turing Machine But Way Worse , 167 byte

0 0 1 1 2 0 0
1 0 1 0 4 0 0
0 1 1 1 2 0 0
1 1 1 1 5 0 0
0 2 1 0 3 0 0
1 2 0 1 1 0 0
0 3 1 1 4 0 0
1 3 0 0 2 0 0
0 4 1 0 0 0 0
1 4 0 1 3 0 0
0 5 1 0 6 0 1
1 5 1 1 2 0 0

Cobalah online!

Harus menjalankan 6-negara 2 simbol 2 Sibuk Berang-berang dari halaman Wikipedia .

7.412×1036534

MilkyWay90
sumber