mi sono imbattuto in questo termine per la prima volta oggi e l'entrata Wikipedia perché in realtà non mi dicono molto:Che cos'è un algoritmo super-ricorsivo?
In teoria della computabilità, algoritmi super-ricorsivi sono un generalizzazione di algoritmi ordinarie che sono più potente, ovvero, calcola più delle macchine di Turing.
Ricorsivo qui non si riferisce a un algoritmo che utilizza se stesso come subroutine; piuttosto, si riferisce alla classe delle funzioni ricorsive, che sono quelle che possono essere calcolate da una macchina di Turing. Una funzione super-ricorsiva, quindi, sarebbe una funzione che una macchina di Turing non è abbastanza potente da calcolare, richiedendo un modello di calcolo più potente.
Ad esempio, il problema di interruzione richiede un algoritmo super-ricorsivo, poiché non è risolvibile utilizzando una normale macchina di Turing.
Vedo, ma ci sono esempi noti di algoritmi super-ricorsivi (ovviamente non ci sarebbe alcuna implementazione effettiva) o conosciamo solo i tipi di problemi che li richiederebbero? – Ferruccio
Conosciamo solo i tipi; il nostro linguaggio ordinario per la descrizione degli algoritmi presuppone una macchina di Turing come modello di calcolo, quindi non ci sarà un esempio nel senso che vorresti. Questa potrebbe essere davvero una buona domanda per cs.stackexchange.com. – chepner
Ehi una volta ottenuta una risposta, puoi anche modificare il tag! –
Questo tag è davvero utile? – MarcioB
@MarcioB Poiché gli algoritmi non calcolabili non sono realizzabili in software più o meno per definizione, probabilmente no. –