Approcci computazionali alla Congettura di Collatz

Questo elaborato presenta uno studio di strategie computazionali volte a verificare la validità della Congettura di Collatz, un problema matematico tuttora irrisolto. Sono presentate alcune strategie tradizionali proposte in letteratura e approcci alternativi (che definiamo "inversi") basati sulla costruzione dell'albero di Collatz. Viene effettuato un confronto per determinare quale processo sia più efficiente a seconda delle condizioni iniziali. Viene proposta una implementazione in linguaggio C di un metodo "ibrido": tale implementazione segue un approccio "inverso" e sfrutta euristicamente un modello probabilistico per ridurne i costi. Sono adottate tecniche per ridurre il consumo di memoria dell'algoritmo e consentire la verifica di numeri arbitrariamente grandi, in particolare viene sfruttato un approccio con Automi Cellulari monodimensionali a sei stati. Vengono infine studiati i costi delle varie tecniche computazionali presentate, accompagnate da un commento sui tempi di esecuzione empiricamente rilevati.