Zur Zeit sind Probleme wie zum Beispiel korrekte Übersetzungen von Texten oder der mathematische Beweis der Existenz unendlich vieler Primzahlzwillinge nicht lösbar.
Was bedeutet "berechenbar"?
Der wohl weitgehendste Ansatz ist der, dass man sagt, dass alles, was mit der Turing-Maschine berechenbar ist, berechenbar ist.
Die unendlich vielen Programme reichen nicht aus, um alle definierbaren Funktionen zu programmieren. Es gibt mehr Teilmengen von N als Elemente von N.
Mit anderen Worten: Die Menge ist über-abzählbar, somit aber auch die Menge aller Funktionen 
Es gibt also nicht-berechenbare Funktionen und damit nicht-programmierbare Aufgaben.
Und es gibt abzählbar viele berechenbare Funktionen (zu jeder gibt es einen entsprechenden Algorithmus).
Churchsche These: Jede (vernünftige) Präzisierung des Begriffes Algorithmus führt auf die gleiche Menge berechenbarer Funktionen.
Anders gesagt:
Jede im intuitiven Sinn berechenbare Funktion ist Turing-berechenbar.
(Dazu muss man natürlich wissen, was eine Turingmaschine ist.)
a) Spontanes Verhalten
Es kann keine Zerfallsvorhersage für ein einzelnes Atom geben, nur die Halbwertszeit für radioaktives Material kann angegeben werden.
b) unzureichende Rechenkapazität
Problem des Handelsreisenden, es ist nur logisch lösbar, ein effizientes Verfahren ist nicht bekannt.
- Applet zur Demonstration des Ameisen-Alg. und des Abkühlungsprozess-Alg.: 
| Aufgabe a) Das Problem des Handelsreisenden ist ein NP-schweres Problem. Arbeiten Sie sich die Bemerkungen zum TSP hier durch und lösen Sie die entsprechenden Aufgaben! |
- NP-schwere Probleme:
c) beweisbar nichtberechenbar
Zerlege einen Winkel in drei gleiche Teile, benutze dafür nur Zirkel und Lineal.
d) Überschreitung der praktisch vorhandenen Rechenkapazität
Zu einer gegebenen Zahl sollen n Punkte untereinander gedruckt werden. Irgendwann streikt jeder Drucker.
e) nichtentscheidbar
- Äquivalenzproblem: (Äquivalenz heißt Gleichwertigkeit.)
Ob bei zwei Programmen für die gleiche
Eingabe die gleiche Ausgabe erzeugt wird, ist nicht
entscheidbar.
Achtung: Es gibt keine allgemein gültige Methode, die Äquivalenz zweier Programme zu beweisen,
wenn diese sogar tatsächlich äquivalent sind.
- Halteproblem
-
Hilbert-Entscheidungsproblem:
Für jede beliebige mathematische Aussage soll geprüft werden, ob sie wahr oder falsch ist. (Anm.: Es gibt zwar Aussagen, die richtig sind, deren Richtigkeit kann aber nicht festgestellt werden.)
- Problem Diophantische Gleichungen : Es soll für eine beliebige Gleichung bestimmt weren, ob sie eine ganzzahlige Lösung hat.
f) ...
Mitunter ist der Rechenauswand so groß, dass man die Geduld, auf die Lösung zu warten, nicht aufbringen möchte oder kann. Beispielsweise ist uns das schon bei der Ausgabe der Fibonaccifolge in Delphi passiert.
a) lineares Wachstum (Aufwand wächst linear mit der Länge der Eingaben.)
Bsp.: Addition zweier gleich langer Zahlen
b) quadratisches Wachstum (Komplexität wächst quadratisch)
Bsp.: Multiplikation zweier gleich langer Zahlen (n Additionen für eine Multiplikation mit n Stellen)
c) exponentielles Wachstum
Bsp.: Alle möglichen Ausstattungsvarianten für einen Komplett-PC
(CPU-Typ, Gehäuse, RAM-Bausteine, Soundkarten, Netzwerkkarten, Netzteile, Anschlüsse, Lüfterarten, Laufwerksarten ...)
würden auf je einer Seite aufgeführt. Das wären 2^n Seiten. Hier wird eine praktische Grenze der Komplexität sichtbar.
Ackermann-Funktion
Zusammenfassend kann gesagt werden, dass nicht alles, was vorstellbar ist, auch programmierbar ist,
dass nicht alles, was sich prinzipiell mit Stift und Papier berechnen lässt, auch programmierbar ist,
und dass mitunter der Aufwand zu hoch für eine Programmentwicklung ist.
Bei einer CD sind etwa nur ein Drittel Aufnahmedaten, der Rest dient der Fehlererkennung und -korrektur.
- Software muss funktionieren und darf (durch Programmierfehler) keinen Schaden beim Anwender anrichten.
Doch ab welchem Zeitpunkt kann man von einer stabilen und fehlerfreien Programmversion sprechen?!
- Immer mehr Probleme gibt es mit Software, die schädlichen Programmcode entählt, die "nach Hause anruft"
oder einfach die Ausführung anderer Programme beeinträchtigt oder gar verhindert (Ausschalten von Sicherheitssoftware)
oder andere Dateien/Programme verändert.
- Besonders lästig ist zur Zeit SPAM (spiced pork and ham) im E-Mail-Postfach.
- Das Urheberrecht muss stets gewahrt sein.
Man kann nur selbsterstellte Bilder und nur die, bei denen abgebildete Personen mit der Veröffentlichung der Bilder
einverstanden sind, ins Netz stellen.
- Der Internetkriminalität (z. Bsp. Identitätsklau) ist nur schwer beizukommen.
- Datenschutz - Recht auf Schutz der eigenen Daten
- Veröffentlichung von Bildern ohne Zustimmung, zum Beispiel in schueler.vz
-
Sicherheit vor Überwachung durch den Staat - "Bundestrojaner" verletzt Privatsphäre
-
Jugendschutz - Nicht alle Seiten im Internet dürfen zum Beispiel nach dem Jugendschutzgesetz Minderjährigen zugänglich sein.
-
Frauenschutz - Die Rechte der Frauen werden im Internet durch diverse Darstellungen missachtet.