Gödel's speed-up theorem
id:
g-del-s-speed-up-theorem-268-870479
title:
Gödel's speed-up theorem
text:
In mathematics, Gödel's speed-up theorem, proved by Gödel (1936), shows that there are theorems whose proofs can be drastically shortened by working in more powerful axiomatic systems. Kurt Gödel showed how to find explicit examples of statements in formal systems that are provable in that system but whose shortest proof is unimaginably long. For example, the statement: is provable in Peano arithmetic (PA) but the shortest proof has at least a googolplex symbols, by an argument similar to the pr
brand slug:
wiki
category slug:
encyclopedia
description:
There are theorems whose proofs can be shortened in more powerful axiomatic systems
original url:
https://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem
date created:
date modified:
2024-01-13T06:55:43Z
main entity:
{"identifier":"Q5626450","url":"https://www.wikidata.org/entity/Q5626450"}
image:
fields total:
13
integrity:
14