Apa masalah "terdekat" dari dugaan Collatz yang telah berhasil diselesaikan?

Saya tertarik pada masalah "terdekat" (dan "paling kompleks") dengan dugaan Collatz yang telah berhasil diselesaikan (yang menurut Erdos terkenal "matematika belum matang untuk masalah seperti itu"). Telah terbukti bahwa kelas masalah "Collatz-like" tidak dapat diputuskan. Namun, masalah yang samar-samar mirip seperti game MIU Hofstadter (diselesaikan, tetapi harus diakui lebih dari masalah mainan) memang dapat diputuskan atau telah diselesaikan.

Pertanyaan-pertanyaan Terkait

Dugaan & Tata Bahasa Collatz / Automata

reference-request open-problem nt.number-theory halting-problem computability vzn
sumber

Karena ini HTML dan bukan LaTeX, lebih mudah jika Anda memasukkan referensi yang relevan.

Suresh Venkat

TCS / sudut empiris pada collatz / ref

vzn

Setidaknya ada satu orang yang mengklaim "dugaan Collatz" adalah jawaban unik untuk pertanyaan Anda. Saya skeptis pada kelengkapan bukti terkait, tapi saya belum menghabiskan cukup waktu menganalisisnya, belum.

Boyd Stephen Smith Jr

Di sini ada makalah baru oleh Michel yang dengan baik mensurvei area yang menghubungkan keraguan terhadap kerangka kerja teori bilangan umum, masalah dalam teori bilangan dari kompetisi berang-berang yang sibuk

vzn

Jawaban:

Komentar panjang:

Urutan seperti collatz dapat dihitung dengan mesin Turing kecil yang memiliki sedikit simbol dan status. Dalam " Mesin Turing Kecil dan kompetisi berang-berang yang digeneralisasi secara umum " oleh P. Michel (2004), ada tabel yang bagus yang menempatkan masalah seperti Collatz antara TM yang dapat didekati (yang masalah penghentiannya dapat ditentukan) dan Universal TM.

enter image description here

Ada TM yang menghitung urutan seperti Collatz yang decidability masih menjadi masalah terbuka: , dan (di mana adalah himpunan Mesin Turing dengan status dan $TM(5,2)$ $TM(3,3)$ $TM(2,4)$ $TM(k,l)$ $k$ $l$ simbol). Saya tidak tahu apakah hasilnya sudah terbukti.

Dari gabungan makalah ini:

... Garis Collatz-like saat ini sudah pada level serendah mungkin, dengan kemungkinan pengecualian $TM(4,2)$ , tetapi kami menduga bahwa semua mesin dalam set ini dapat dibuktikan ...

Lihat juga " Kompleksitas mesin Turing universal kecil: survei " oleh D. Woods dan T. Neary (2007).

Contoh lain dari masalah seperti Collatz yang decidability merupakan masalah terbuka adalah sistem tag Post: ; untuk analisis terbaru lihat " Pada batas solvabilitas dan unsolvabilitas dalam sistem tag. Hasil Teoritis dan Eksperimental " oleh L. De Mol (2009). $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$

Marzio De Biasi
sumber

untuk melengkapi jawabannya: Conway menunjukkan bahwa ada urutan seperti Collatz yang tidak dapat ditentukan ams.org/mathscinet-getitem?mr=392904 . yaitu urutan collatz-like itu sendiri dapat mensimulasikan mesin turing universal.

Sasho Nikolov

Terima kasih! survei mitchell / hasilnya sangat keren! Untuk klarifikasi dalam tabel, "T" dalam sel menunjukkan TM (k, l) telah terbukti ada yang setara dengan dugaan collatz. perspektif ini juga menunjukkan bahwa dugaan collatz bukan hanya keingintahuan teoritis yang terisolasi tetapi mungkin fenomena permukaan dari sesuatu yang lebih dalam dalam teori komputabilitas. ps juga sangat tertarik jika ada "masalah collatz like" yang pernah terbuka pernah dipecahkan ...?

vzn

Pertimbangkan fungsi , di mana ketika adalah genap dan ketika adalah ganjil. Maka diketahui bahwa untuk setiap , terdapat sehingga . $T: \mathbb N \rightarrow \mathbb N$ $T(n)=n/2$ $n$ $T(n)=n+1$ $n$ $n \in \mathbb N$ $k \in \mathbb N$ $T^{(k)}(n)=1$

$T(n)=n+1$ $n$ $T(n)=3n+1$ $n$

Craig Feinstein
sumber

Saya tidak berpikir ini memuaskan bagian "paling rumit" dari pertanyaan, karena siswa sekolah dasar yang termotivasi dapat mengidentifikasi ide kunci di balik bukti pernyataan Anda dengan sedikit pemikiran.

Yonatan N

Tetapi jika itu lebih kompleks dan masih diselesaikan, itu tidak akan menyerupai dugaan Collatz lagi. Lebih jauh, judul pertanyaannya menunjukkan bahwa ia mengutamakan "terdekat" daripada "paling kompleks".

Craig Feinstein