Algorithmische Informationstheorie - Versionsgeschichte

SchlurcherBot: Bot: http → https

2025-11-01T16:40:12Z

Bot: http → https

← Nächstältere Version		Version vom 1. November 2025, 17:40 Uhr
Zeile 23:		Zeile 23:
	== Weblinks ==		== Weblinks ==
	* [[Gregory Chaitin]]: [https://www.cs.auckland.ac.nz/~chaitin/howto.html ''How to Run Algorithmic Information Theory on a Computer''.] (englisch)		* [[Gregory Chaitin]]: [https://www.cs.auckland.ac.nz/~chaitin/howto.html ''How to Run Algorithmic Information Theory on a Computer''.] (englisch)
	* [~~http~~://www.astronews.com/news/artikel/2004/12/0412-005.shtml Komprimierte Nachrichten von Aliens mit Rauschen identisch]		* [https://www.astronews.com/news/artikel/2004/12/0412-005.shtml Komprimierte Nachrichten von Aliens mit Rauschen identisch]
	* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}		* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}
	* {{Webarchiv \| url=http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html \| wayback=20131213010842 \| text=G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} (abgerufen per Archive org. am 5. Januar 2018)		* {{Webarchiv \| url=http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html \| wayback=20131213010842 \| text=G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} (abgerufen per Archive org. am 5. Januar 2018)

Haraldmmueller: /* Mathematischer Hintergrund */ dt.

2020-10-20T10:14:17Z

Mathematischer Hintergrund: dt.

← Nächstältere Version		Version vom 20. Oktober 2020, 11:14 Uhr
Zeile 12:		Zeile 12:

	== Mathematischer Hintergrund ==		== Mathematischer Hintergrund ==
	Der Ansatz von [[Andrei Kolmogorow]] lässt als Algorithmen Programme für beliebige [[Turingmaschine]]n zu. Gregory Chaitin setzt die Kolmogorow-Komplexität zur [[Rekursionstheorie\|Theorie rekursiver Funktionen]] (~~Siehe~~ auch [[µ-Rekursion]], [[Lambda-Kalkül]]) und dem Werk von [[Kurt Gödel]] in Beziehung. Er beschränkt die möglichen Programme auf solche, die selbst wieder auf einer speziellen Variante der [[Universelle Turingmaschine\|universellen Turingmaschine]] (UTM) laufen, auf der so genannten ''selbst-limitierenden universellen Turingmaschine''.		Der Ansatz von [[Andrei Kolmogorow]] lässt als Algorithmen Programme für beliebige [[Turingmaschine]]n zu. Gregory Chaitin setzt die Kolmogorow-Komplexität zur [[Rekursionstheorie\|Theorie rekursiver Funktionen]] (siehe auch [[µ-Rekursion]], [[Lambda-Kalkül]]) und dem Werk von [[Kurt Gödel]] in Beziehung. Er beschränkt die möglichen Programme auf solche, die selbst wieder auf einer speziellen Variante der [[Universelle Turingmaschine\|universellen Turingmaschine]] (UTM) laufen, auf der so genannten ''selbst-limitierenden universellen Turingmaschine''.

	~~Nach~~ ~~dem~~ ~~Beweis~~ von Chaitin kann allerdings nicht grundsätzlich festgestellt werden, ob eine Zeichenkette algorithmisch weiter verkürzt werden kann. So können beispielsweise neue und effektivere Kompressionsalgorithmen gefunden werden oder eine scheinbar zufällige Zahlenfolge kann von einem Pseudozufallszahlengenerator stammen. Wegen des [[Halteproblem]]s können auch nicht alle Turingmaschinen, die kleiner als eine gegebene Zeichenfolge sind, in endlicher Zeit durchprobiert werden.		Gemäß einem Theorem von Chaitin kann allerdings nicht grundsätzlich festgestellt werden, ob eine Zeichenkette algorithmisch weiter verkürzt werden kann. So können beispielsweise neue und effektivere Kompressionsalgorithmen gefunden werden oder eine scheinbar zufällige Zahlenfolge kann von einem Pseudozufallszahlengenerator stammen. Wegen des [[Halteproblem]]s können auch nicht alle Turingmaschinen, die kleiner als eine gegebene Zeichenfolge sind, in endlicher Zeit durchprobiert werden.

	== Literatur ==		== Literatur ==

ⵓ: 1 externer Link geändert

2019-08-20T15:34:09Z

1 externer Link geändert

← Nächstältere Version		Version vom 20. August 2019, 16:34 Uhr
Zeile 25:		Zeile 25:
	* [http://www.astronews.com/news/artikel/2004/12/0412-005.shtml Komprimierte Nachrichten von Aliens mit Rauschen identisch]		* [http://www.astronews.com/news/artikel/2004/12/0412-005.shtml Komprimierte Nachrichten von Aliens mit Rauschen identisch]
	* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}		* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}
	* ~~[https://wayback.archive.org/web/20131213010842/~~http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics] (abgerufen per Archive org. am 5. Januar 2018)		* {{Webarchiv \| url=http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html \| wayback=20131213010842 \| text=G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} (abgerufen per Archive org. am 5. Januar 2018)
	* [http://sammelpunkt.philo.at:8080/1520/1/bromand.pdf Über erkenntnistheoretische Implikationen der algorithmischen Informationstheorie] (abgerufen am 5. Januar 2018)		* [http://sammelpunkt.philo.at:8080/1520/1/bromand.pdf Über erkenntnistheoretische Implikationen der algorithmischen Informationstheorie] (abgerufen am 5. Januar 2018)

Joergens.mi am 12. Mai 2019 um 06:08 Uhr

2019-05-12T06:08:55Z

← Nächstältere Version		Version vom 12. Mai 2019, 07:08 Uhr
Zeile 9:		Zeile 9:
	: <code>1111111100000000</code>		: <code>1111111100000000</code>

	Während die erste Folge durch Münzwurf als [[Zufallsgenerator]] erzeugt wurde, kann die zweite Folge jedoch durch die Anweisung „schreibe 8-mal 1 dann 8-mal 0“ verkürzt werden. Im Sinne der algorithmischen Informationstheorie hat die erste Folge deshalb mehr '''algorithmische Information''', da sie viel schwieriger oder gar nicht verkürzt werden kann. Die algorithmische Information ist umso höher, je weniger eine Zeichenkette (unter anderem durch [[Datenkompression]]) komprimiert werden kann. [[Zufall\|Zufällige]] Zahlenfolgen und [[weißes Rauschen]] enthalten in der Regel keine vorhersagbaren Muster und sind deshalb nicht komprimierbar – der algorithmische Informationsgehalt ist deshalb höher.		Während die erste Folge durch Münzwurf als [[Zufallsgenerator]] erzeugt wurde, kann die zweite Folge jedoch durch die Anweisung „schreibe 8-mal 1 dann 8-mal 0“ verkürzt werden. Im Sinne der algorithmischen Informationstheorie hat die erste Folge deshalb mehr '''algorithmische Information''', da sie viel schwieriger oder gar nicht verkürzt werden kann. Die algorithmische Information ist umso höher, je weniger eine Zeichenkette (unter anderem durch [[Datenkompression]]) komprimiert werden kann. [[Zufall\|Zufällige]] Zahlenfolgen und [[Weißes Rauschen (Physik)\|weißes Rauschen]] enthalten in der Regel keine vorhersagbaren Muster und sind deshalb nicht komprimierbar – der algorithmische Informationsgehalt ist deshalb höher.

	== Mathematischer Hintergrund ==		== Mathematischer Hintergrund ==

Aka: /* Beispiel */ Tippfehler entfernt

2018-11-30T09:45:28Z

Beispiel: Tippfehler entfernt

← Nächstältere Version		Version vom 30. November 2018, 10:45 Uhr
Zeile 9:		Zeile 9:
	: <code>1111111100000000</code>		: <code>1111111100000000</code>

	Während die erste Folge durch Münzwurf als [[Zufallsgenerator]] erzeugt wurde, kann die zweite Folge jedoch durch die Anweisung „schreibe 8-mal 1 dann 8-mal 0“ verkürzt werden. Im Sinne der algorithmischen Informationstheorie hat die erste Folge deshalb mehr '''algorithmische Information''', da sie viel schwieriger oder gar nicht verkürzt werden kann. Die algorithmische Information ist umso höher, je weniger eine Zeichenkette (unter ~~Anderem~~ durch [[Datenkompression]]) komprimiert werden kann. [[Zufall\|Zufällige]] Zahlenfolgen und [[weißes Rauschen]] enthalten in der Regel keine vorhersagbaren Muster und sind deshalb nicht komprimierbar – der algorithmische Informationsgehalt ist deshalb höher.		Während die erste Folge durch Münzwurf als [[Zufallsgenerator]] erzeugt wurde, kann die zweite Folge jedoch durch die Anweisung „schreibe 8-mal 1 dann 8-mal 0“ verkürzt werden. Im Sinne der algorithmischen Informationstheorie hat die erste Folge deshalb mehr '''algorithmische Information''', da sie viel schwieriger oder gar nicht verkürzt werden kann. Die algorithmische Information ist umso höher, je weniger eine Zeichenkette (unter anderem durch [[Datenkompression]]) komprimiert werden kann. [[Zufall\|Zufällige]] Zahlenfolgen und [[weißes Rauschen]] enthalten in der Regel keine vorhersagbaren Muster und sind deshalb nicht komprimierbar – der algorithmische Informationsgehalt ist deshalb höher.

	== Mathematischer Hintergrund ==		== Mathematischer Hintergrund ==

Invisigoth67: form

2018-07-26T14:52:39Z

form

← Nächstältere Version		Version vom 26. Juli 2018, 15:52 Uhr
Zeile 17:		Zeile 17:

	== Literatur ==		== Literatur ==
	* Günther Hotz:''Algorithmische Informationstheorie''. Band 25, Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen, B.G. Teubner Verlagsgesellschaft, Stuttgart 1997, ISBN 978-3-8154-2310-3.		* Günther Hotz: ''Algorithmische Informationstheorie.'' Band 25, Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen, B.G. Teubner Verlagsgesellschaft, Stuttgart 1997, ISBN 978-3-8154-2310-3.
	* Dirk W. Hoffmann:''Grenzen der Mathematik''. Eine Reise durch die Kerngebiete der mathematischen Logik, 2. Auflage, Springer Verlag, berlin / Heidelberg 2013, ISBN 978-3-642-34719-1.		* Dirk W. Hoffmann: ''Grenzen der Mathematik.'' Eine Reise durch die Kerngebiete der mathematischen Logik, 2. Auflage, Springer Verlag, berlin / Heidelberg 2013, ISBN 978-3-642-34719-1.
	* Lienhard Pagel:''Information ist Energie''. Definition eines physikalisch begründeten Informationsbegriffes, Springer Fachmedien, Wiesbaden 2013, ISBN 978-3-8348-2611-4, S. 68–70.		* Lienhard Pagel: ''Information ist Energie.'' Definition eines physikalisch begründeten Informationsbegriffes, Springer Fachmedien, Wiesbaden 2013, ISBN 978-3-8348-2611-4, S. 68–70.

	== Weblinks ==		== Weblinks ==

Aka: Halbgeviertstrich

2018-01-05T19:51:18Z

Halbgeviertstrich

← Nächstältere Version		Version vom 5. Januar 2018, 20:51 Uhr
Zeile 19:		Zeile 19:
	* Günther Hotz:''Algorithmische Informationstheorie''. Band 25, Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen, B.G. Teubner Verlagsgesellschaft, Stuttgart 1997, ISBN 978-3-8154-2310-3.		* Günther Hotz:''Algorithmische Informationstheorie''. Band 25, Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen, B.G. Teubner Verlagsgesellschaft, Stuttgart 1997, ISBN 978-3-8154-2310-3.
	* Dirk W. Hoffmann:''Grenzen der Mathematik''. Eine Reise durch die Kerngebiete der mathematischen Logik, 2. Auflage, Springer Verlag, berlin / Heidelberg 2013, ISBN 978-3-642-34719-1.		* Dirk W. Hoffmann:''Grenzen der Mathematik''. Eine Reise durch die Kerngebiete der mathematischen Logik, 2. Auflage, Springer Verlag, berlin / Heidelberg 2013, ISBN 978-3-642-34719-1.
	* Lienhard Pagel:''Information ist Energie''. Definition eines physikalisch begründeten Informationsbegriffes, Springer Fachmedien, Wiesbaden 2013, ISBN 978-3-8348-2611-4, S. ~~68-70~~.		* Lienhard Pagel:''Information ist Energie''. Definition eines physikalisch begründeten Informationsbegriffes, Springer Fachmedien, Wiesbaden 2013, ISBN 978-3-8348-2611-4, S. 68–70.

	== Weblinks ==		== Weblinks ==

Pittimann: /* Weblinks */ + 1

2018-01-05T16:22:13Z

Weblinks: + 1

← Nächstältere Version		Version vom 5. Januar 2018, 17:22 Uhr
Zeile 26:		Zeile 26:
	* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}		* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}
	* [https://wayback.archive.org/web/20131213010842/http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics] (abgerufen per Archive org. am 5. Januar 2018)		* [https://wayback.archive.org/web/20131213010842/http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics] (abgerufen per Archive org. am 5. Januar 2018)
			* [http://sammelpunkt.philo.at:8080/1520/1/bromand.pdf Über erkenntnistheoretische Implikationen der algorithmischen Informationstheorie] (abgerufen am 5. Januar 2018)

Pittimann: - 1

2018-01-05T16:07:53Z

- 1

← Nächstältere Version		Version vom 5. Januar 2018, 17:07 Uhr
Zeile 25:		Zeile 25:
	* [http://www.astronews.com/news/artikel/2004/12/0412-005.shtml Komprimierte Nachrichten von Aliens mit Rauschen identisch]		* [http://www.astronews.com/news/artikel/2004/12/0412-005.shtml Komprimierte Nachrichten von Aliens mit Rauschen identisch]
	* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}		* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}
	* [[Günter Hotz]]: [http://www-hotz.cs.uni-sb.de/H-BIB/Berichte/FB14-97-01.ps.gz ''Algorithmische Informationstheorie'' (Teil 1).] ([[Gzip]]; 272 kB) Technical Report FB14-97-01, Universität des Saarlandes, FB 14 Informatik, Januar 1997
	* [https://wayback.archive.org/web/20131213010842/http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics] (abgerufen per Archive org. am 5. Januar 2018)		* [https://wayback.archive.org/web/20131213010842/http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics] (abgerufen per Archive org. am 5. Januar 2018)

Pittimann: /* Weblinks */ + 1

2018-01-05T16:07:12Z

Weblinks: + 1

← Nächstältere Version		Version vom 5. Januar 2018, 17:07 Uhr
Zeile 26:		Zeile 26:
	* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}		* {{Scholarpedia\|http://www.scholarpedia.org/article/Algorithmic_information_theory}}
	* [[Günter Hotz]]: [http://www-hotz.cs.uni-sb.de/H-BIB/Berichte/FB14-97-01.ps.gz ''Algorithmische Informationstheorie'' (Teil 1).] ([[Gzip]]; 272 kB) Technical Report FB14-97-01, Universität des Saarlandes, FB 14 Informatik, Januar 1997		* [[Günter Hotz]]: [http://www-hotz.cs.uni-sb.de/H-BIB/Berichte/FB14-97-01.ps.gz ''Algorithmische Informationstheorie'' (Teil 1).] ([[Gzip]]; 272 kB) Technical Report FB14-97-01, Universität des Saarlandes, FB 14 Informatik, Januar 1997
			* [https://wayback.archive.org/web/20131213010842/http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics] (abgerufen per Archive org. am 5. Januar 2018)




	[[Kategorie:Informationstheorie]]		[[Kategorie:Informationstheorie]]