• calcolabilità
• computability
• numeri surreali
• surreal numbers

Si vuole indagare se esista una nozione naturale di calcolabilità sul Campo dei numeri surreali, in maniera simile alle note nozioni di calcolabilità sui reali e sugli ordinali. Verranno analizzati in particolare due sistemi molto naturali di notazioni, che conducono a nozioni di surreali calcolabili intensionalmente ed estensionalmente differenti.

Una prima maniera di effettivizzare i surreali, visti come sequenze di segni alla Gonshor, è mediante una costruzione analoga a quella degli ordinali costruibili alla Kleene, ma ammettendo due diversi successori. Questo cattura l'intuizione di sequenze di segni calcolabili, ma le operazioni di somma e prodotto di anello non sono calcolabili su tali indici. L'insieme dei reali che, visti come surreali, sono calcolabili come sequenze di segni, è esattamente l'insieme dei reali calcolabili nel senso classico.

Una differente nozione di calcolabilità è ottenuta effettivizzando la definizione ricorsiva dei surreali alla Conway come tagli. Questa nozione di calcolabilità è algebricamente molto ricca, ed e.g. le operazioni di campo, l'esponenziale sono calcolabili. Inoltre, i surreali calcolabili come tagli sono esattamente quegli con una sequenza di segni iperaritmetica, e tale equivalenza può essere resa effettiva. In particolate, i reali con sequenza di cifre iperaritmetica ma non ricorsiva non sono reali calcolabili, ma, visti come surreali, sono calcolabili come tagli.


English translation:

We wish to study whether there exists a natural notion of computability on the Field of surreal numebrs, in a similar fashion as the well-known notions of computability on real and ordinal numbers. Two particularly natural systems of notations will be considered, that lead to intensionally and extensionally different notions of computable surreals.

A first way of effectivizing the surreals, saw as sequences of signs à la Gonshor, is through a construction analogous to that of Kleene's constructible ordinals, but admitting two different successors. This captures the intuition of computable sign sequences, but the ring operations fail to be computable on those indexes. The set of reals that, when seen as surreals, are computable as sequences of signs, is exactly the set of computable reals in the classical sense.

A different notion of computability is derived by effectivizing the recursive definition of the surreals as cuts à la Conway. This notion of computability is algebraically very rich, and e.g. the field operations, as well as the exponential, are computable. Moreover, the surreals computable as cuts are exactly those with an hyperarithmetic sign sequence, and the equivalence can be made effective. In particular, reals whose sequence of digit is hyperarithmetic, but not recursive, are not computable reals, but, when seen as surreals, are computable as cuts.