---
title: 'Unentscheidbarkeit für Java-Programmierer'
url: 'https://tutego.de/blog/javainsel/2010/03/unentscheidbarkeit-fur-java-programmierer'
markdown: 'https://tutego.de/blog/javainsel/2010/03/unentscheidbarkeit-fur-java-programmierer.md'
date: '2010-03-05'
description: 'Es wird niemals eine Software geben, die sich eine andere Software anschaut und entscheidet, ob sie etwas bestimmtes macht. In der theoretischen Informatik gibt es das Halteproblem. Man kann kein Programm schreiben, das sich ein anderes beliebiges Programm anschaut und nach endlich vielen Schritten…'
taxonomy:
  category:
    - Allgemein
---

# Unentscheidbarkeit für Java-Programmierer

![Illustration einer tropischen Insel mit Palmen und einem hohen Berg](https://tutego.de/blog/javainsel/user/themes/tutego/images/insel-cover.jpg)# Java Blog für Programmierer

[Java Blog für Programmierer](https://tutego.de/blog/javainsel/)

## Unentscheidbarkeit für Java-Programmierer

05.03.2010 · [Christian Ullenboom](https://tutego.de/blog/javainsel/author/admin/)

Es wird niemals eine Software geben, die sich eine andere Software anschaut und entscheidet, ob sie etwas bestimmtes macht. In der theoretischen Informatik gibt es das **Halteproblem**. Man kann **kein** Programm schreiben, das sich ein anderes **beliebiges** Programm anschaut und nach endlich vielen Schritten erkennt, ob es hält. (Es kann auch interpretiert werden, aber man hat nicht beliebig Zeit. Wenn ein Programm exakt 10 Jahre läuft, kann man das nicht „testen“, da der Test ja auch 10 Jahren dauert.) **Nehmen wir an** es gibt ein Programm **bollean `willStop`( char\[\] program )**
das entscheidet, ob ein anderes Programm endet. So sollte folgendes **`true`** ergeben:

```java
willStop("return");
willStop("for(int i=0;i<100000000;i++)print(i);");
```

und folgendes **`false`:**

```
willStop("while(true);");
```

Eine **zweites Methode**:

```java
void reverser( char[] program ) {
 while ( willStop( program ) )
 out.println( "willStop will stop" );
}
```

Umgangssprachlich: – Wenn **`willStop()`** `true` liefert, endet **`reverser()`** nicht. – Wenn **`willStop()`** `false` liefert, endet **`reserver()`**. Frage: Was passiert bei folgendem Aufruf?

```java
void reverser( "void reverser(char[]..." );
```

Ausgefaltet:

```java
void reverser( char[] program ) {
 while ( willStop( "void reverser(char[]..." ) )
 out.println( "willStop will stop" );
}
```

Stoppt **`reserver()`**, hat **`willStop`(„void reserver…“)** aber **`false`** gegeben. Aber warum ergibt **`willStop()`** dann **`false`**? Die Funktion stoppt doch? (Umgekehrtes gilt auch.) Durch diesen Widerspruch muss die Annahme falsch sein, dass es **`willStop()`** überhaupt gibt.

[Aus dem Seminar: Codeanalyse mit FindBugs, PMD, Checkstyle und JDepend](http://www.tutego.de/seminare/java-schulung/findbugs-pmd-checkstyle-jedepend.html)

Kategorien: [Allgemein](https://tutego.de/blog/javainsel/category/allgemein/)

## 5 Kommentare

**Anonymous** · [12.03.2010 08:34](#comment-50)

Muss denn alles relevant und finanziell verwertbar sein? Es ist halt ein schöner Beweis. Bei einem Kunstwerk fragt man doch auch nicht, ob es relevant ist.

**Martin Wildam** · [09.03.2010 02:30](#comment-49)

Wir haben in der Schule in Mathematik auch mal einen "Beweis" durchgemacht, bei dem rausgekommen ist, daß 0=1 Irgendwo war natürlich ein versteckter Fehler - aber wie relevant sind solche Theorien?

**Marius** · [06.03.2010 03:06](#comment-45)

Nur durch Ausführen, kann man in der Tat nie erkennen, dass ein Programm nicht endet. Durch die Analyse des Codes kann man es bei manchen Programmen aber doch erkennen. Man kann ja z.B. nachgucken, ob while-true-Schleifen kein breake; enthalten. Dann weiß man, dass (in Java) das Programm nicht enden kann. Ich finde daher, dass es insgesamt etwas zu verallgemeinert ist. BTW sind in dem Satz "Kann man kein Programm schreiben, das sich ein anderes Programm anschaut und nach endlich vielen Schritten erkennt, ob es hält." die ersten beiden Wörter verdreht.

**Christian Ullenboom** · [05.03.2010 20:55](#comment-44)

Ähem, ja. Fehler ist korrigiert.

**Jürgen** · [05.03.2010 20:11](#comment-43)

Danke, \*\*schöne\*\* Erinnerungen an Theoretische Infomatik! Aber es sollte wohl heißen \*Umgangssprachlich: \\- Wenn willStop() \*\*true\*\* ergibt, endet reverser() nicht. \\- Wenn willStop() \*\*false\*\* ergibt, endet reserver().\*

Die bisherigen Kommentare wurden aus WordPress übernommen. Neue Kommentare sind derzeit geschlossen.

[← Alle Beiträge](https://tutego.de/blog/javainsel/)

---

## Navigation

- Previous: [Buchkritik “Google Web Toolkit . GWT Java AJAX Programming. A practical guide to Google Web Toolkit for creating AJAX applications with Java”](https://tutego.de/blog/javainsel/2010/03/buchkritik-%e2%80%9cgoogle-web-toolkit-gwt-java-ajax-programming-a-practical-guide-to-google-web-toolkit-for-creating-ajax-applications-with-java%e2%80%9d.md)
- Next: [Smart GWT 2.1 ist raus](https://tutego.de/blog/javainsel/2010/03/smart-gwt-2-1-ist-raus.md)