Fisikawan Lev Landau memainkan permainan mental dengan angka Soviet [
1 ]. Tablet-tablet itu berbentuk dua angka, tanda hubung, dua angka lagi, dan beberapa huruf.
Aturan gim
Permainannya adalah menerapkan operator matematika ke angka di kedua sisi dasbor sehingga dasbor dapat diganti dengan tanda sama dengan. Misalnya, jika Anda mengambil plat nomor 44-74, salah satu solusinya adalah
4! + 4 = 7 * 4Harap dicatat bahwa kami dapat memasukkan operator seperti
! ,
+ dan
* , tetapi tanpa menambahkan angka.
Apakah ada solusi untuk setiap plat nomor yang memungkinkan? Tergantung pada operator mana yang Anda izinkan untuk digunakan.
Anda dapat meremehkan permainan dengan menerapkan operasi bagian fraksional {x} di kedua sisi, karena bagian fraksional dari bilangan bulat adalah nol. Anda dapat melarang operator bagian pecahan dengan alasan bahwa ini jelas bukan operasi matematika sekolah menengah, atau hanya melarangnya karena itu membuat permainan tidak menarik.
Terjemahan didukung oleh EDISON Software , yang berinvestasi dalam startup yang menjanjikan , dan juga mengembangkan berbagai layanan cloud .
Solusi satu atap
Ternyata ada solusi universal, dimulai dengan pengamatan itu
√ (n + 1) = sec arctan √ n.
Jika satu sisi lebih besar dari yang lain, rumus di atas memberikan solusi segera. Misalnya, solusi untuk nomor plat 89-88 adalah
√89 = sec arctan√88.
Jika perbedaannya lebih besar, rumusnya dapat diterapkan berulang kali. Misalnya, kita bisa menerapkan rumus dua kali untuk mendapatkan
√ (n + 2) = sec arctan√ (n + 1) = sec arctan sec arctan√ n
dan karena itu solusi yang memungkinkan untuk 35-37 adalah
sec arctan sec arctan √35 = √37.
Kompleksitas kolmogorov
Mengingat bahwa suatu solusi selalu memungkinkan, kita dapat membuat game lebih menarik dengan menemukan solusi yang paling sederhana. Kami memiliki pemahaman intuitif tentang apa artinya ini. Dengan contoh kita 44-74, solusi pertama
4! + 4 = 7 * 4
lebih sederhana dari solusi universal
sec arctan sec arctan ... √44 = √74
yang akan membutuhkan penggunaan garis potong dan arctangents 30 kali.
Kompleksitas Kolmogorov dari sebuah objek adalah panjang dari program komputer terpendek untuk membuat objek. Kita dapat menghitung kompleksitas Kolmogorov dari fungsi-fungsi yang diterapkan pada angka-angka di setiap sisi untuk mengukur seberapa kompleks solusinya.
Untuk mengetahuinya, kita perlu menunjukkan bahasa pemrograman yang kita miliki, dan tidak sesederhana kelihatannya. Jika kita menganggap notasi matematika sebagai bahasa pemrograman, apakah kita ingin menghitung! suka satu karakter dan arctan suka 6 karakter? Ini sepertinya tidak benar. Jika kami menulis "arctan" sebagai "atn", kami akan menggunakan lebih sedikit karakter tanpa membuat solusi lain.
Kompleksitas kode python
Untuk membuat hal-hal lebih objektif, kita dapat mempertimbangkan panjang program komputer nyata, daripada menyajikan notasi matematika sebagai bahasa pemrograman. Katakanlah kita memilih Python. Maka berikut adalah beberapa fungsi yang dihitung oleh dua solusi pelat nomor 44-74 kami.
from math import sqrt, cos, atan def f(): sec = lambda x: 1/cos(x) y = sqrt(44) for _ in range(30): y = sec(atan(y)) return y def g(): return sqrt(77)
Kita dapat mengukur kompleksitas fungsi kita f dan g dengan menghitung jumlah karakter di masing-masing. Tetapi masih ada kesulitan.
Bagaimana dengan impor? Panjangnya harus diperhitungkan dengan f karena menggunakan semua pernyataan yang diimpor, tetapi g menggunakan pernyataan yang lebih pendek yang hanya mengimpor sqrt. Lebih mendasar lagi, apakah kita bodoh bahkan mengimpor perpustakaan?
Selain itu, dua fungsi yang disebutkan di atas tidak memberikan hasil yang persis sama karena akurasi yang terbatas. Kita dapat membayangkan bahwa fungsi impor kita jauh akurat, tetapi kemudian kita tidak benar-benar menggunakan Python, melainkan versi ideal dari Python.
Bagaimana dengan loop? Ini memperkenalkan angka baru, 3 dan 0, dan karenanya melanggar aturan permainan Landau. Jadi haruskah kita membuka gulungan sebelum menghitung kompleksitas?
Eksperimen pemikiran
Kompleksitas Kolmogorov adalah konsep yang sangat berguna, tetapi lebih merupakan eksperimen mental daripada apa yang dapat Anda hitung secara praktis. Kita dapat membayangkan program terpendek untuk menghitung sesuatu, tetapi kita jarang tahu bahwa kita benar-benar menemukan program semacam itu. Yang bisa kita ketahui dalam praktik adalah batas atas.
Secara teoritis, Anda dapat membuat daftar semua mesin Turing dengan panjang tertentu atau semua program Python dari panjang tertentu dan menemukan yang terpendek yang melakukan tugas ini, tetapi daftar tumbuh secara eksponensial dengan meningkatnya panjang.
Namun, dimungkinkan untuk menghitung durasi program tertentu jika kita menghadapi beberapa kesulitan yang disebutkan di atas. Kami bisa menjadikan Landau permainan untuk dua orang dengan melihat siapa yang dapat menawarkan solusi yang lebih sederhana dalam waktu yang tetap.
Kembali ke Landau
Jika kami mengizinkan sinus dan gelar dalam set operator kami, maka B.S. Gorob adalah solusi universal. Untuk n ≥ 6, n! kelipatan 360, dan sebagainya
sin (n!) ° = 0.
Dan jika n kurang dari 6, representasi dua digitnya dimulai dari nol, jadi kita bisa mengalikan angka untuk mendapatkan nol.
Jika kita melarang fungsi transendental, kita memblokir trik Gorobets dan kita memiliki fungsi yang panjangnya dapat kita ukur secara obyektif dalam bahasa pemrograman.