Googology Wiki
Register
Advertisement
Googology Wiki

anyone have an idea why 2^1000 was chosen? WikiRigbyDude (talk) 14:17, August 26, 2014 (UTC)

Is \(\Sigma(2^{1000})\) a transcedental integer? Wythagoras (talk) 10:03, September 6, 2014 (UTC)
I think so. With \(2^{1000}\) states we can quite surely compute functions beyond the scope of ZFC. But I cannot prove that this is the case. LittlePeng9 (talk) 10:42, September 6, 2014 (UTC)
While to be sure we would have to program a TM that searched through all ZFC proofs, it is inconceivable that this could not be done in fewer than 2^1000 states. (I would guess fewer than 10000 is possible.) Deedlit11 (talk) 10:57, September 6, 2014 (UTC)
We can't prove that a k-state BB can't be proven to be halt in just k symbols? Wythagoras (talk) 11:41, September 6, 2014 (UTC)
No, because given TM we don't know a priori that it's a busy beaver. LittlePeng9 (talk) 12:48, September 6, 2014 (UTC)
Did you mean k states rather than k symbols? In that case, the answer is yes, we can. Let's say we have a TM that runs through all ZFC proofs of n steps or less that uses m states. We can use p states to output a number of size \(\Sigma(p)\), so we can use m + p states to check all ZFC proofs of size \(\Sigma(p)\) states or less. For sufficiently large p, we will have \(\Sigma(p) > m+p\), so for sufficiently large k we can verify that a k-state BB halts using fewer than k states (assuming the halting is provable in ZFC). Deedlit11 (talk) 00:53, September 7, 2014 (UTC)
How can a ZFC proof have "k states"? LittlePeng9 (talk) 06:15, September 7, 2014 (UTC)

Are transcendental integers well-defined?[]

Definition 1. For turing machine \(M\), let \(T(M)\) be the execution time of \(M\).

Proposition 2. For all integers \(n\), there exists a turing machine \(M\) such that \(T(M) > n\).

Proof. Consider a turing machine \(M\) such that:

  1. \(Q = {q_0, q_1, q_2, ..., q_n, q_{n+1}}\) where \(Q\) is the set of states.
  2. \(q_0\) is the initial state.
  3. \(q_{n+1}\) is the halting state.
  4. For all \(k < n+1\), \(q_k\) will transit to \(q_{k+1}\) regardless of the tape content.

\(M\) will run \(n+1\) steps and halt.∎

Proposition 3. Proposition 2. is provable within \(ZFC\) using at most \(2^{1000}\) symbols.

Sketch of a proof. Write down the proof of proposition 2. in a formal language and count the symbols of the proof.∎

Proposition 4. Any integers are not transcendental.

Proof. Assume \(n\) is a transcendental integer. By proposition 2., there exists a TM \(M\) such that \(T(M) > n\). By proposition 3. and the definition of transcendental integers, \(n ≥ T(M)\) which is a contradiction.∎Vyv03354 (talk) 03:18, October 15, 2017 (UTC)

Here is the flaw in this reasoning: Even though ZFC proves "for every \(n\) there is a TM halting after more than \(n\) steps" in less than \(2^{1000}\) symbols, it doesn't follow that for every single \(n\) ZFC proves "there is a TM halting after more than \(n\) steps". The reason this doesn't go through immediately is that the statement "there is a TM halting after more than \(n\) steps" for some particular \(n\) needs to include a description of this particular \(n\) in the statement, which can easily take us above \(2^{1000}\) symbols if \(n\) is large. LittlePeng9 (talk) 08:07, October 15, 2017 (UTC)
The definition of transcendental integers does not require a proof for the statement "there is a TM halting after more than \(n\) steps". It only requires "\(M\) halts". The length limit does not apply to the description of \(n\).
But I understand your point. Even if ZFC proves "for every \(n\) there is a TM \(M\) halting after more than \(n\) steps" in less than \(2^{1000}\) symbols, it doesn't follow that for every single \(n\) there is a TM \(M\) and ZFC proves that "\(M\) halts" in less than \(2^{1000}\) symbols and \(M\) halts after more than \(n\) steps, because the latter requires a description of a particular \(M\). In my example, it is almost the same as the description of \(n\). Correct? Vyv03354 (talk) 10:54, October 15, 2017 (UTC)
Exactly, that's the idea. LittlePeng9 (talk) 11:12, October 15, 2017 (UTC)
Flaw in flaw: ZFC proves "for all n, there's a TM halting only after more than n steps", giving infinitely many special cases. Choose the one with n=2^E3, and success. Also, a flaw in the name: \(\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{A}\Rightarrow\mathbb{Z}\subset\mathbb{A}\). 80.98.179.160 15:16, March 13, 2018 (UTC)

Proof system[]

If lengths of proofs of a given formula can differ between pairwise-equivalent proof systems (a combination of logical axioms and rules of inference), which proof system is used for the proofs so that the lengths of the proofs are <2^1000? C7X (talk) 15:40, August 3, 2020 (UTC)

You can choose any reasonable one. (Friedman did not try to create a specific large number, and hence did not have to fix a strict way to define "lengths of proof".) At least, the replacment of the system by a standard system does not significantly change the growth rate of the corresponding function.
p-adic 21:41, August 3, 2020 (UTC)
Advertisement