turing reduction

Fetched 2026-10-26 (cache).

Synonyms: string reduction

Antonyms: string reduction

Related words from Datamuse; suggestions, not definitions.

Noun

1. {{lb|en|algorithm}} A [[reduction]] that [[solve]]s 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''.

Source: Wiktionary · CC BY-SA 4.0 (Wiktionary dump) · cached copy, not a rewrite.