non-computable
Beyond machine calculation
Non-computable describes a problem or function that no algorithm can solve in principle—not merely difficult or slow, but mathematically impossible to compute.
A non-computable function cannot be calculated by any computer program, no matter how powerful or how much time is allowed.
The halting problem—determining whether an arbitrary program will eventually stop or run forever—is the classic example: Turing proved the halting problem is non-computable.
The term belongs to computability theory and theoretical computer science.
Accepted starting principles
- proofsDemonstrations of truth
- theoremDemonstrated logical conclusion
- conjectureGuess from limited facts
- formalismPrivileging structure over substance
intractability · infinity · diagonalization · syntax · semantics · formalization · undefinability · Tarski
Lacking possible proof
- decidabilityAlgorithmic resolution capability
- diagonalizationReducing to diagonal form
- enumerationSequential listing of items
axioms
Accepted starting principles
- proofsDemonstrations of truth
- theoremDemonstrated logical conclusion
- conjectureGuess from limited facts
formalism · intractability · infinity · diagonalization · syntax · semantics · formalization · undefinability · Tarski · incompleteness
undecidable
Lacking possible proof
- decidabilityAlgorithmic resolution capability
- diagonalizationReducing to diagonal form
- enumerationSequential listing of items
oracle
Authoritative wisdom source
non-computablecomputable
Able to be algorithmically determined
decidable · calculable · recursive · solvable · algorithmic
non, compute, computable, computation, computational, computationally, computer, computers, computing