Die Turing-Maschine
Die Church-Turing-These
- Church undTuring stellten unabhängig voneinander folgende Behauptung auf: »Wenn ein Problem, welches in eine Turing-Maschine eingegeben wird, von dieser nicht gelöst werden kann, so kann das Problem auch nicht von Menschen gelöst werden.
- Der Umkehrschluß bedeutet dann, daß alles, was vom Menschen gedacht oder gewußt werden kann, auch berechenbar ist (von einer Turing-Maschine lösbar).
- (nach
[KURZ93], S. 117)
