Gödel, in his early thoughts on computational complexity, noted that a mechanical method that could solve any problem would revolutionize mathematics: If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n2), this would have consequences of the greatest importance.
În primele sale gânduri despre complexitatea computațională, Gödel observa că o metodă mecanică care ar putea rezolva orice problemă ar revoluționa matematica: „Dacă chiar ar exista o mașină cu φ(n) ∼ k ⋅ n (sau chiar ∼ k ⋅ n2), aceasta ar avea consecințe de cea mai mare importanță.