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
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