Ist die Überprüfung, ob die Länge eines C-Programms, das eine Zeichenfolge erzeugen kann, weniger als eine bestimmte Anzahl entschieden wird?

Question

Ich erhielt diese Frage:

Komplexität (en) ist die Länge des kleinsten C-Programms, das die Zeichenfolge S als Ausgang erzeugt.Ist die Frage "Komplexität (en)

In Bezug auf die Entgleisbarkeit weiß ich nur über das Haltingproblem und lernte nur von Rice's Theorem, während ich online sucht (obwohl ich nicht glaube, dass es hier angewendet werden kann?).Ich konnte das Problem nicht zu einem unentscheidbaren Problem reduzieren, das ich kenne.Vielen Dank im Voraus für jede Hilfe

Answer 1

Die Länge des kleinsten C-Programms, das eine bestimmte Zeichenfolge erzeugt, ist als Kolmogorov-Komplexität der Zeichenfolge.Eine der Grundeigenschaften von Kolmogorov-Komplexität ist seine Unentschlossenheit.