Generalized Collatz Functions, które są nierozstrzygalne
: 2 sie 2021, o 01:57
Stuart A. Kurtz i Janos Simon w publikacji "The Undecidability of the Generalized Collatz Problem" wykazali, że pewne generalizacje problemu Collatza są nierozstrzygalne (właściwie to Conway udowodnił to wcześniej, oni tylko uprościli jego dowód, ale nie dotarłem do jego dowodu). Definiują oni te funkcje tak:
Funkcja \(\displaystyle{ g}\) jest funkcją Collatza, jeśli istnieje liczba całkowita \(\displaystyle{ m}\) oraz dodatnie liczby wymierne \(\displaystyle{ a_{i}, b_{i} : i < m}\), takie, że zawsze, gdy \(\displaystyle{ x \equiv i \mod m}\), to \(\displaystyle{ g(x) = a_{i} \cdot x + b_{i}}\) jest liczbą całkowitą.
Ta definicja wyczerpuje definicję ciągów Collatza, jeśli dobrze rozumiem, tylko gdy \(\displaystyle{ i}\) numerujemy od zera, wtedy definicja ciągu Collatza (wersja "1,5x+0,5"), wygląda tak:
\(\displaystyle{ m=2}\)
\(\displaystyle{ a_{0}=0,5}\)
\(\displaystyle{ b_{0}=0}\)
\(\displaystyle{ a_{1}=1,5}\)
\(\displaystyle{ b_{1}=0,5}\)
Zgadza się? Czy dobrze rozumiem tę definicję? Oczywiście możemy wprowadzić kolejne \(\displaystyle{ a_{i}}\) oraz \(\displaystyle{ b_{i}}\), jeśli zwiększymy modulus, ale wtedy nie będzie to już definicja ciągu Collatza.
Dodano po 2 godzinach 9 minutach 10 sekundach:
Temat do zamknięcia. W publikacji, którą wymieniłem "The Undecidability of the Generalized Collatz Problem", autorzy podają dokładnie tę definicję problemu Collatza:
Funkcja \(\displaystyle{ g}\) jest funkcją Collatza, jeśli istnieje liczba całkowita \(\displaystyle{ m}\) oraz dodatnie liczby wymierne \(\displaystyle{ a_{i}, b_{i} : i < m}\), takie, że zawsze, gdy \(\displaystyle{ x \equiv i \mod m}\), to \(\displaystyle{ g(x) = a_{i} \cdot x + b_{i}}\) jest liczbą całkowitą.
Ta definicja wyczerpuje definicję ciągów Collatza, jeśli dobrze rozumiem, tylko gdy \(\displaystyle{ i}\) numerujemy od zera, wtedy definicja ciągu Collatza (wersja "1,5x+0,5"), wygląda tak:
\(\displaystyle{ m=2}\)
\(\displaystyle{ a_{0}=0,5}\)
\(\displaystyle{ b_{0}=0}\)
\(\displaystyle{ a_{1}=1,5}\)
\(\displaystyle{ b_{1}=0,5}\)
Zgadza się? Czy dobrze rozumiem tę definicję? Oczywiście możemy wprowadzić kolejne \(\displaystyle{ a_{i}}\) oraz \(\displaystyle{ b_{i}}\), jeśli zwiększymy modulus, ale wtedy nie będzie to już definicja ciągu Collatza.
Dodano po 2 godzinach 9 minutach 10 sekundach:
Temat do zamknięcia. W publikacji, którą wymieniłem "The Undecidability of the Generalized Collatz Problem", autorzy podają dokładnie tę definicję problemu Collatza:
Nie doczytałem, bo też nie jest to poziom publikacji, w które byłbym w stanie wczytywać się ze zrozumieniem.This is a natural generalization: the function \(\displaystyle{ k(x)}\) of the Collatz Problem has this form for \(\displaystyle{ m = 2}\), \(\displaystyle{ a_{0} = \frac{1}{2}}\), \(\displaystyle{ b_{0} = 0}\),\(\displaystyle{ a_{1} = 3}\), and \(\displaystyle{ b_{1} = 1}\).