(Asking whether a system ever halts is equivalent to asking whether there exists a number of steps t at which the system can be determined to be in its halting state.)

In 1900, as one of his list of 23 important mathematical problems, David Hilbert posed the problem of finding a single finite procedure that could systematically determine whether a solution exists to any specified Diophantine equation.

No single shape is known which has the property that it can tile the plane only non-repetitively, although one strongly suspects that one must exist.

Outside of science, relativity theory is sometimes given as evidence for various general ideas of cultural relativism (compare page 1131 )—which have existed since well before relativity theory in physics, and seem in the end to have no meaningful connection to it.

The idea that human language is constructed from words according to definite grammatical rules has existed since at least around perhaps 500 BC when Panini gave a grammar for Sanskrit. … The notion of using definite rules to organize and maneuver formations of soldiers appears to have existed in Babylonian and Assyrian times, and to be well codified by Roman times. … Geometric and arithmetic puzzles surprisingly close to those common today seem to have existed since as long ago as 2000 BC.

And for several decades additional so-called large cardinal axioms have been discussed, that in effect state that sets exist larger than any that can be reached with the current axioms of set theory.

The idea that it might be possible to construct machines or other inanimate objects that could emulate human thinking existed already in antiquity, and became increasingly popular starting in the 1600s. … Turing made the prediction that by 2000 a computer would exist that could pass the so-called Turing test and be able to imitate a human in a conversation. ( René Descartes had discussed a similar test for machines in 1637, but concluded that it would never be passed.)

He imagined that this field itself existed in a vacuum—but that it was produced by a mass such as a star at its center. … (And no purely repetitive solutions can exist.)

[Universal] register machines The results of page 100 suggest that with 2 registers and up to 8 instructions no universal register machines (URMs) exist.

Diagonalization arguments analogous to those on pages 1128 and 1162 show that in principle there must exist functions that can be evaluated only by computations that exceed any given bound.