Informatik

Was besagt die Church-Turing-These?

Alles, was intuitiv algorithmisch berechenbar ist, ist durch eine Turingmaschine berechenbar.

Es ist keine mathematisch beweisbare Aussage, sondern eine These über den Begriff "Algorithmus".