Sta controllando se la lunghezza di un programma C che può generare una stringa è inferiore a un dato numero decidabile?

Question

Mi è stato dato questa domanda:

Komplexity (s) è la lunghezza del programma C più piccolo che genera la stringa s come uscita.È la domanda "Komplexity (s)

Per quanto riguarda la decidabilità, conosco solo il problema fermante e ho appena saputo del teorema del riso durante la ricerca online (anche se non penso che possa essere applicato qui?).Non ho potuto ridurre il problema a qualsiasi problema indecidabile, lo so.Grazie in anticipo per qualsiasi aiuto

Answer 1

La lunghezza del programma C più piccolo che genera una determinata stringa è nota come complessità di Kolmogorov della stringa.Una delle proprietà di base della complessità di Kolmogorov è la sua indecisione.