Metraipolis › archive › dc_db61d01f03e8

Turing riduzione — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Turing_riduzione
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-10T04:44:27.003Z
SHA-256 of the archived text
43996e8229083658e5519b72d1604a692293c70ebb6581cb8636872d39446879
Stable URL of this page
https://metraipolis.com/documento/dc_db61d01f03e8

How to cite

Turing riduzione — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Turing_riduzione (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_db61d01f03e8 (Metraipolis archive dc_db61d01f03e8, sha256 43996e8229083658e5519b72d1604a692293c70ebb6581cb8636872d39446879)
BibTeX
@misc{dcdb61d01f03e8,
  title = {Turing riduzione — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Turing_riduzione},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_db61d01f03e8; sha256 43996e8229083658e5519b72d1604a692293c70ebb6581cb8636872d39446879},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Turing_riduzione. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In teoria della computabilità, una Turing-riduzione da un problema decisionale A ad un problema decisionale B è una macchina oracolo che decide il problema A dato un oracolo per B (Rogers 1967, Soare 1987). Può essere inteso come un algoritmo che potrebbe essere utilizzato per risolvere A se avesse a sua disposizione una subroutine per la risoluzione di B. Il concetto può essere applicato in modo analogo ai problemi di funzione. Se esiste una Turing-riduzione da A a B, allora ogni algoritmo per B può essere utilizzato per produrre un algoritmo per A, inserendo l'algoritmo per B in ogni punto in cui la macchina oracolo che computa A interroga l'oracolo per B. Tuttavia, poiché la macchina oracolo può interrogare l'oracolo un numero elevato di volte, l'algoritmo risultante potrebbe asintoticamente richiedere più tempo rispetto all'algoritmo per B o alla macchina oracolo che computa A. Una Turing-riduzione in cui la macchina oracolo computa in un tempo polinomiale è nota come riduzione di Cook. La prima definizione formale di computabilità relativa, poi chiamata riducibilità relativa, fu data da Alan Turing nel 1939 in termini di macchine oracoli. Successivamente, nel 1943 e nel 1952 Stephen Kleene definì un concetto equivalente in termini di funzioni ricorsive. Nel 1944 Emil Post usò il termine "riducibilità di Turing" per riferirsi al concetto.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Turing riduzione» — https://it.wikipedia.org/wiki/Turing_riduzione
Wikidata Q4489310: «concept in computability theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4489310
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Turing_riduzione?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 147737419, consultata il 2026-11-10T04:41:29.673Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 6342032a9d21ad73a20b63c33fdd8c7f5df08617e02c4742e5c89767644ff1ed