Turing reduction

noun

Turing reduction

noun

Etymology After Alan Turing.

1

Computing, Computing theory, Engineering, Mathematics, Natural sciences, Physical sciences, Sciences A reduction that solves a problem if the solution to another problem is already known, i.e. an algorithm that could be used to solve A if it had available to it a subroutine for solving B.

Related terms
Cook reduction, oracle machine

Entry derived from the Wiktionary, under licence CC BY-SA 4.0 — list of authors.