No label defined (Q4070738)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3489016
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3489016

      Statements

      0 references
      1973
      0 references
      Sei \( X=\{0,1\}^* \backslash e \cup\{0,1\}^{nz}\), d.h. jedes \(x \in X\) eine endliche (Wort) oder unendliche binäre Folge. Zwei Folgen heißen koordiniert, wenn \(x=y\) oder \(y=x\). A heißt berechenbare Abbildung, wenn \(A\) eine abzählbare Menge von Paaren \([x, y]\) mit folgender Eigenschaft ist: wenn \([x, y] \in A\) und \([x', y'] \in A\) und \(x\) ist mit \(x'\) koordiniert, dann ist auch \(y\) koordiniert mit \(y'\). Sei \(a\) eine endliche oder unendliche Folge. Dann sind alle Wörter \(y\) mit \((x \subset a \rightarrow[x, y] \in A)\) Anfangsstücke elner Folge \(b\) (endlich oder unendlich), diese Folge heißt Bild der Folge \(a\), d. h. \(A(a)=b\) (Yu. T. Medvedev). Die minimale Länge eines binären Wortes \(x\) mit \(A(x)=y\) heißt monotone Komplexität des Wortes \(y\) bzgl. der Abbildung \(A(km_A(y))\). Der Verf. gibt ohne Beweis an, daß für \(P\)-fast alle \(a\) die (universalisierte) monotone Komplexität \(km(a[1, n]) \) in der Nähe des Logarithmus der Wahrscheinlichkeit \(P(a[1, n])\) liegt, wobei \(P\) eine beliebige berechenbare Wahrscheinlichkeitsvertellung auf der Menge der Folgen von natürlichen Zahlen und \(a[1, n]\) das Anfangsstück von \(a\) der Länge \(n\) ist. Damit wird ein Resultat von \textit{A. N. Kolmogorov} [Probl. Peredachi Inf. 1, No. 1, 3--11 (1965; Zbl 0271.94018)], das für die Kolmogorovsche Komplexität \(K\varphi(x)\), \(\varphi\) partiell-rekursive Funktion, und die Gleichverteilung gilt, verallgemeinert, wobei \(K\varphi(x)\) durch \(km(x)\) ersetzt wird. Ohne Beweis sind weitere Resultate, Insbesondere zur Zufälligkeit im Sinne von Martin-Löf (Theorem 3), angegeben.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references