Wiki Googologie
Advertisement
Wiki Googologie

Les entiers transcendantaux sont un ensemble de nombres énormes, définis par Harvey Friedman.

Si n est un entier, nous l'appelons transcendantal si la condition suivante est remplie : soit M une machine de Turing, telle qu'il existe une preuve dans ZFC d'une longueur maximale de 21000 montrant que M s'arrête. Alors M s'arrête en au plus n étapes. En d'autres termes, n est supérieur ou égal au temps d'arrêt de toute machine de Turing dont la preuve ZFC de l'arrêt est d'une longueur maximale de 21000.

Propriétés

It is clear that if m>n and n is transcendental, then so is m. Equivalently, transcendental integers are upwards closed, and consequently there is a smallest transcendental integer.

Friedman suspects that this kind of numbers should naturally arise in Boolean relation theory. It is very likely that transcendental integers quickly appear in Friedman's finite promise games, because corresponding functions outgrow all provably recursive functions of SMAH, which is strong extension of ZFC. However, no specific examples of nontrivial transcendental integers are known.

Extension

A function naturally arises from the definition of a transcendental integer. It is further extended to TR function.

Bonne définition

Even when we are working in ZFC set theory, the well-definedness of the least transcendental integer is non-trivial, as we do not have a proof of the Σ1-soundness of ZFC set theory by Goedel's incompleteness theorem.

Indeed, the inconsistency of ZFC set theory itself, i.e. ¬Con(ZFC), might be provable under ZFC set theory. In that case, the statement "The termination of any Turing Machine is provable under ZFC set theory" is provable under ZFC set theory. Now readers are supposed to understand how non-trivial the well-definedness of the least transcendental integer is. In fact, it is known that the least transcendental integer is well-defined in the sense that it is meta-theoretically provable that the existence of the least transcendental integer is provable under ZFC set theory. However, if we try to explicitly write down the proof of the well-definedness following the meta-theoretic proof, then the resulting proof is of length 21000.

For the issue, see the article of TR function.

Références

Advertisement