Permutasi Amusical dan Masalah yang Tidak Dapat Diselesaikan

Hello, Selamat datang di wikitanic.com.

John Horton Conway (1937–2020) pada tahun 2009 [Photo (c) Denise Applewhite, Princeton University]

Dalam penghargaan memorial di Notices of the American Mathematical Society (Ryba, et al, 2022), Dierk Schleicher menulis tentang bagaimana dia meyakinkan John Conway untuk menerbitkan makalah, “Tentang masalah aritmatika yang tidak dapat diselesaikan”, yang mencakup diskusi tentang Permutasi Amusik. Makalah ini, yang membahas pernyataan aritmatika yang hampir pasti benar tetapi kemungkinan besar tidak dapat dibuktikan, terpilih untuk “The Best Writing on Mathematics” edisi 2014, yang diterbitkan oleh Princeton University Press [Pitici, 2014]. Permutasi Amusik adalah upaya untuk menemukan urutan sederhana yang perilakunya tidak dapat diputuskan.

Dugaan Collatz

Peta Collatz didefinisikan secara sederhana. Ini adalah peta pada bilangan asli: bilangan genap $2n$ dipetakan ke $N$ ; angka ganjil $N$ dipetakan ke $3n+1$ . Ini dikenal sebagai peta HOTPO (HOTPO = Half Atau Triple Plus One). Sejak $N$ ganjil, nomor $3n+1$ harus genap, kita dapat menggabungkan dua langkah dan menulis peta dalam bentuk padat

$\displaystyle 2n \rightarrow n \,, \qquad 2n - 1 \rightarrow 3n - 1 \,. \ \ \ \ \ (1)$

Peta ini, untuk argumen dari 1 sampai 100, diilustrasikan pada Gambar di bawah ini.

Peta Collatz (padat). $C:\mathbbN\rightarrow\mathbbN$ untuk 100 nomor pertama.

Ketika peta Collatz diulang, urutan angka diperoleh. Eksperimen numerik menunjukkan bahwa, dalam semua kasus, urutan yang muncul dari peta yang diringkas (1) memasuki siklus $1\rightarrow2\rightarrow1$ atau sederhana $(1,2)$ . Itu Dugaan Collatz adalah bahwa siklus ini dicapai dari semua nilai awal $N$ tapi tidak ada bukti yang pernah ditemukan.

Conway (2013) berspekulasi bahwa Konjektur Collatz “tidak dapat diselesaikan”. Maksudnya, hal itu tidak dapat dibuktikan atau disangkal dari aksioma dasar teori himpunan. Itu ditunjukkan oleh Kurt Gödel pada tahun 1931 bahwa selalu ada masalah yang tidak dapat diputuskan, dan Conway, yang curiga bahwa masalah seperti itu mungkin sangat umum, bertanya apa pernyataan benar paling sederhana yang tidak dapat dibuktikan atau disangkal. Dia membahas sejumlah kandidat, termasuk fungsi Collatz, dan menganalisis kasus tertentu, yang disebutnya permutasi musikal.

Permutasi Amusik

Automorfisme $\Pi : \mathbbN\rightarrow\mathbbN$ dapat didefinisikan sebagai berikut:

$\displaystyle \beginarrayrcl 2n & \longleftrightarrow & 3n \\ 4n - 3 & \longleftrightarrow & 3n - 2 \\ 4n - 1 & \longleftrightarrow & 3n - 1 \,. \endarray$

Kami mencatat bahwa, berbeda dengan peta Collatz, fungsi ini dapat dibalik, sehingga dapat “dijalankan” di kedua arah. Tindakan fungsi pada yang pertama $100$ angka ditunjukkan pada Gambar berikut:

Permutasi lucu untuk 100 angka pertama.

Conway mempresentasikan empat siklus terbatas, yang dia yakini sebagai satu-satunya siklus untuk peta tersebut:

Jika Kalian ingin mencari jawaban lainya, Baca Juga : Bagaimana Satu Sekolah Meningkatkan Keterlibatan dan Keyakinan Matematika

$\displaystyle (1) \quad (2,3) \quad (4,6,9,7,5 ) \quad (44,66,99,74,111,83,62,93,70,105,79,59) \, .$

Dia juga mencantumkan beberapa nilai dari apa yang diduga sebagai urutan tak terbatas. Tidak ada bukti yang tersedia, tetapi bukti numeriknya meyakinkan. Misalnya, urutan mulai dari angka 8 dihitung sebanyak 200.000 iterasi, ketika nilainya melebihi $10^5000$ . Hampir tidak mungkin untuk percaya bahwa istilah dengan nilai 8 akan pernah muncul kembali.

Argumen probabilistik mendukung pernyataan bahwa tidak ada lagi siklus berhingga. Sebuah angka $N$ akan dikalikan (kurang-lebih) dengan $\frac32$ jika bahkan atau oleh $\frac34$ jika ganjil. Mari kita asumsikan bahwa nilai genap dan ganjil dari $N$ sama-sama mungkin. Kemudian, rata-rata jumlahnya dikalikan dengan $\sqrt \frac32\times\frac34 = \sqrt \frac98$ . Dalam dua belas iterasi peta, faktornya adalah

$\displaystyle \frac3^122^18 \kira-kira 2,027 \,, \ \ \ \ \ (2)$

atau perkiraan penggandaan. Jadi, begitu jumlahnya besar, sangat sulit untuk membayangkan bahwa ia akan kembali ke nilai kecil untuk menyelesaikan siklusnya. Ini bukan bukti apa pun, tetapi “secara probabilistik jelas” atau, seperti yang dikatakan Conway, jelas.

Mengapa “Amusik”?

Dalam penyetelan Pythagoras, seluruh tangga nada kromatik dihasilkan dari urutan seperlima musik, dengan nada yang memiliki rasio frekuensi $3:2$ . Ketika produk melebihi $2$ , pindah ke oktaf yang lebih tinggi, itu diperkecil setengahnya. Setelah dua belas iterasi, faktornya adalah

$\displaystyle \frac3^122^19 \kira-kira 1,0136 \,. \ \ \ \ \ (3)$

Jika faktor ini sama dengan 1, siklus akan tertutup, tetapi rasio kekuatan 2 dan 3 tidak mungkin sama dengan 1. Perbedaan kecil ini dikenal sebagai diskrepansi enharmonik, dan rasio dalam (3) disebut koma Pythagoras. Ini adalah inspirasi untuk nama Conway yang lucu “permutasi musikal”.

Kesimpulan

Conway menyarankan bahwa tidak hanya pernyataan bahwa 8 dalam siklus tak terbatas tidak dapat diselesaikan, tetapi ini kegelisahan itu sendiri tidak dapat dibuktikan, dan seterusnya, dalam tumpukan implikasi logis yang tak terbatas.

Untuk dugaan Collatz, seperti yang ditulis dalam bentuk padat (1), peta diskalakan dengan $\frac12$ atau $\frac32$ dengan probabilitas yang sama, sehingga faktor pertumbuhan yang diharapkan adalah $\sqrt3/4 <1$ . Jadi, kita dapat berpendapat bahwa peta itu seharusnya mungkin siklus kembali ke 1. Namun demikian, dalam catatan tambahan, Conway menulis bahwa dugaan Collatz kemungkinan besar tidak dapat diselesaikan.