Le grandi domande della vita: Pi e il problema della fermata

Forse una delle domande più interessanti tra quelle cui sono incappato nell'ultimo periodo su Quora: la differenza tra \(\pi\) e la costante di Chaitin in termini di computabilità.
La costante di Chaitin, introdotta da Gregory Chaitin, è stata una delle protagoniste del bel volume Darwin alla prova, testo sull'evoluzione, ma anche sulla matematica, e successivamente ne ho scritto all'interno del post sull'immortalità quantistica.
Vale, però, la pena rivedere la sua definizione.

Fermarsi o non fermarsi?

La costante venne introdotta da Chaitin all'interno dei suoi studi intorno al problema della fermata. A stabilire tale problema fu Alan Turing. Di fatto la domanda è: dato un arbitrario programma per computer, ci si chiede se finirà mai la sua elaborazione o se proseguirà per sempre. Turing, nel 1936, utilizzando la sua macchina di Turing, dimostrò che non esiste nessun algoritmo in grado di risolvere il problema della fermata per tutti i possibili programmi. Fondamentalmente, restando all'interno dei teoremi di incompletezza di Kurt Godel, il problema della fermata è indecidibile.
Più o mneno intorno al 2006 Chaitin introdusse la costante \(\Omega\), che porta il suo nome, come la probabilità che un programma genberato casualmente si fermi. Tale probabilità è definita dall'espressione: \[\Omega = \sum_{{ p }} 2^{-p} = \sum_i 2^{-p_i}\] dove \(\lbrace p \rbrace\) è una collezione di stringhe di varie lunghezze. Tale espressione rende la costante di Chaitin trascendentale, come \(\pi\), sebbene si potrebbe tranquillamente obiettare che, in effetti, \(\Omega\) non è esattamente una costante... a meno di non prendere in considerazione lo spazio di tutte le possibili stringhe, e allora sì che potremmo considerare la omega di Chaitin (altro nome con cui è conosciuta) una costante.
E qui vediamo, quindi, la principale differenza con \(\pi\): per \(\Omega\) conosciamo un'unica espressione, ma poiché non conosciamo un bel nulla su tutto il resto, non siamo in grado di calcolare tale costante; \(\pi\), invece, è legata a un oggetto geometrico, quindi abbiamo un punto di partenza per determinare il suo valore.

Figli di \(\pi\)

Come ho raccontato nel video fresco di stampa (lo trovate qui sotto in chiusura di post), la trascendenza di pi greco rende impossibile la quadratura del cerchio esatta usando riga e compasso. Quindi non esiste nessun numero reale diverso da \(\pi\) che moltiplicato per \(\pi\) fornisca un numero almeno irrazionale. L'unico modo è utilizzare frazioni di \(\pi\), ma chi ha posto la domanda in un commento ha escluso tale possibilità dalle risposte che avrebbe voluto ricevere. E quindi dobbiamo a malincuore fornire una risposta negativa.