Infinite Non Determinism

The possibility to non-deterministically explore an infinite number of possible branches (e.g. f(x) for all natural numbers x).

Such a device would allow algorithms or machines, that are beyond TuringEquivalent. They could e.g. solve the HaltingProblem and many other undecidable problems.

See NonDeterministic NonDeterministicTuringMachine, QuantumComputersArentTuringEquivalent

EditText of this page (last edited September 2, 2009) or FindPage with title or text search