Generalized Collatz Functions, które są nierozstrzygalne

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Generalized Collatz Functions, które są nierozstrzygalne

Post autor: matemix »

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:
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}\).
Nie doczytałem, bo też nie jest to poziom publikacji, w które byłbym w stanie wczytywać się ze zrozumieniem.
ODPOWIEDZ