Ogni problema risolvibile può essere risolto utilizzando un qualsiasi schema di algoritmo?

-2

Recentemente ho iniziato a leggere la teoria dietro gli algoritmi. Ho quindi iniziato a pensare a "cosa accadrebbe se avessimo astratto problemi e algoritmi, in modo da poter implementare un sistema generico in grado di risolvere la maggior parte dei problemi". Purtroppo non sono riuscito a trovare informazioni su questo argomento. Credo che la programmazione logica sia piuttosto vicina, ma non penso che sarebbe facile creare una libreria con qualcosa del genere.

Come suggerisce la domanda, questo 'algoritmo generico' risolverebbe solo 'problemi generici' e i problemi dovranno ovviamente essere risolti (provati) in primo luogo. Ho pensato che ogni problema che è risolvibile attraverso ciò che Wikipedia definisce come "algoritmi di progettazione" ( link ) è un buon candidato.

Quindi la domanda reale diventa qualcosa di più: "Possiamo definire un problema astratto risolvibile con un algoritmo astratto, che impiega Backtracking, Divide & Conquer ecc.?".

Penso che una cosa del genere sia possibile, che esista una tale rappresentazione astratta di un problema che può essere risolta da uno qualsiasi di questi algoritmi.

    
posta RabbitBones22 15.09.2017 - 19:34
fonte

1 risposta

5

No, a causa dell'esplosione combinatoria . Leggi anche (come commentato da CandledOrange ) su P vs NP

Alcuni problemi (ad esempio il problema dei saleman in viaggio ) sono in teoria risolvibili, ma in pratica intrattabile

Molte domande pratiche rientrano in questa categoria (ad es. ottimizzazione dei compilatori , cryptography )

Alcuni problemi sono irrisolvibili (ad esempio possono essere ridotti al problema di interruzione ), in particolare la maggior parte delle domande su analisi del codice sorgente statico (se vuoi risposte affidabili e valide), ad es. rilevamento statico di perdite di memoria . Vedi anche Teorema di Rice .

I problemi intrattabili o irrisolvibili (o quelli mal definiti) sono in realtà abbastanza comuni, ed è per questo che la programmazione è divertente.

(in pratica, quando inizi a pensare a un programma, chiediti: il problema è equivalente al problema dell'arresto? Il problema è intrattabile?)

Leggi anche su I teoremi di incompletezza di Gödel e Problemi di Hibert .

Leggi assolutamente Gödel, Escher, Bach di D.Hofstadter. È un libro molto buono, divertente da leggere.

Esamina anche AGI . Leggi il blog di J.Pitrat.

    
risposta data 15.09.2017 - 19:39
fonte

Leggi altre domande sui tag