Wiki Googologie
Advertisement
Wiki Googologie

SCG(13) est un grand nombre défini avec une fonction à croissance rapide SCG(k) utilisant un théorème de Robertson-Seymour de théorie des graphes conçu par Harvey Friedman.[1] Friedman a déclaré que SCG(13) est plus grand que le temps d'arrêt de toute machine de Turing telle qu'on peut prouver qu'elle s'arrête en au plus 22000 symboles dans -CA0, et donc bien plus grand que TREE(3).

Fonction SCG(k)

A subcubic graph is a finite graph in which each vertex has a valence of at most three, i.e. no vertex is connected to more than three edges. (For the sake of this article, subcubic graphs are allowed to be multigraphs, and are not required to be connected.) We also define the graph minor relation as follows: A is said to be a graph minor of B if we can derive A from the following process: start with B, remove vertices and edges, and contract edges.[2] An example of a graph minor derivation is shown in the infobox of this article.

Given an integer k, suppose we have a sequence of subcubic graphs G1, G2, ... such that each graph Gi has at most i + k vertices and for no i < j is Gi homeomorphically embeddable into Gj (i.e. is a graph minor).

The Robertson-Seymour theorem proves that subcubic graphs are well-quasi-ordered by homeomorphic embeddability, implying such a sequence cannot be infinite. So, for each value of k, there is a sequence with maximal length. We denote this maximal length using SCG(k).

Specific values

It is possible to show that SCG(0) = 6. The first graph is one vertex with a loop, the second is two vertices connected by a single edge, and the next four graphs consist of 3, 2, 1, and 0 unconnected vertices. All maximal sequences will peak and decline this way. The following bounds have been claimed by Googology Wiki user Hyp cos.[3]

  • \(\text{SCG}(1) > f_{\varepsilon_22}(f_{\varepsilon_02}(f_{\varepsilon_0+1}(f_{\varepsilon_0}(f_{\omega^\omega+1}(f_{\omega^5+\omega^2+\omega}(\\f_{\omega^23+1}(f_{\omega^22+1}(f_{\omega^2+\omega3+1}(f_{\omega^2+1}(f_{\omega^2}(3\times2^{3\times2^{95}})))))))))))\).
  • \(\text{SCG}(2) > f_{\vartheta(\Omega^\omega)}(f_{\varepsilon_22}(f_{\varepsilon_02}(f_{\varepsilon_0+1}(f_{\varepsilon_0}(f_{\omega^\omega+1}(\\f_{\omega^5+\omega^2+\omega}(f_{\omega^23+1}(f_{\omega^22+1}(f_{\omega^2+\omega3+1}(f_{\omega^2+1}(f_{\omega^2}(3\times2^{3\times2^{95}}))))))))))))\)

These bounds use a non-standard choice of fundamental sequences for ordinals — by using a particular, highly complex bijection between ordinals and small graphs, which we will denote here by f, we define \(\alpha[n]=\max\{\beta: \beta<\alpha\text{ and } f(\beta)\text{ is a graph with }\leq n\text{ vertices}\}\).

Since the graph indices start at one, it is also valid to say that SCG(-1) = 1, consisting only of the empty graph.

Friedman stated that SCG(13) is greater than the halting time of any Turing machine such that it can be proven to halt in at most 22,000 symbols in \(\Pi^1_1\)-\(\text{CA}_0\), and therefore far larger than TREE(3).[1]

Références

  1. 1,0 et 1,1 Harvey Friedman, html FOM 279:Subcubic Graph Numbers/restated
  2. Technically a topological minor, but topological minors and graph minors are equivalent for subcubic graphs.
  3. Hyp cos. SCG(n) and some related 8 August 2014.
Advertisement