Informatik gehört zusammen mit Mathematik zu den Strukturwissenschaften.
Eine der 4 Richtungen der Informatik ist die theoretische Informatik.
Es wird darin nach absoluten Aussagen gesucht:
z.B. Gibt es berechenbare Probleme und nicht berechenbare, entscheidbare Probleme, die mit ja oder nein enden.
Dann gibt es ein möglichst klein gehaltenes abstraktes Ding, das quasi einen Computer darstellt: Die Turingmaschine.
Nach der These von Church http://de.wikipedia.org/wiki/These_von_Church gilt das:
„Die Klasse der turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“
Die Turing-Maschine besteht im wesentlichen aus Zuständen, Zustandsübergängen und einem gedachten Band auf dem man sich nur mit eins nach links eins nach rechts oder bleiben bewegen kann. Damit sollen alle denkbaren Berechnungen möglich sein. Dabei kann man mit einer Turingmaschine eine andere Turingmaschine simulieren, mit einer bestimmten Kodierung. Damit ist dann gezeigt, dass auch die Programmierbarkeit gegeben ist.
Die theoretische Informatik sagt dabei etwas über die Wirklichkeit aus, anstelle einfach nur über Computer.
Man kann z.B. beweisen, dass es für spezielle Probleme keine Lösung mit besserer Laufzeitkategorie gibt.
Alle NP-Entscheidungsprobleme lassen sich zurückführen auf das Erfüllungsproblem der Aussagenlogik. Schon das finde ich ziemlich krass. Das sind alle Entscheidungsprobleme, die eine nicht-deterministische polynomielle Laufzeit haben.
Ich glaube man kann dann zwar nicht sagen, dass man die Wirklichkeit auf Logik reduzieren kann, aber man kann einen Teil der Wirklichkeit auf Logik reduzieren und zwar die Wirklichkeit, bei der es um ja oder nein geht oder 2 andere Zustände als Ergebnis und die Wirklichkeit die NP-Laufzeit hat.