CAI will be interpreted in a broad sense: in principle, any way in which a computer can assist instruction will be considered a part of this field.

Die Church-Turing-These besagt, dass jede Funktion, die intuitiv "berechenbar" ist, auch mit einer Turing- Maschine berechnet werden kann.

Exorciser is a framework for exercises in an introductory course on the Theory of Computation where students test their mastery of basic concepts while the system’s fine-grained grading pinpoints the source of any misunderstanding.

Es gibt keine Turing- Maschine, die entscheiden kann, ob eine beliebige andere Turing-Maschine je anhält oder nicht.

Unterricht mit der Informatik als Unterrichtsgegenstand

Informatikunterricht soll also eine Einführung in die Wissenschaft bezeichnen, nicht das Vermitteln von Anwenderfertigkeiten (z.B. Datenbankabfrage, Einsatz eines bestimmten Textverarbeitungssystems) und nicht den Einsatz des Computers im Unterricht (z.B. als Multimedia-Gerät).

Kara ist eine Mini-Umgebung basierend auf der Idee der endlichen Automaten. Kara, der Marienkäfer , lebt in einer einfachen grafischen Welt auf dem Bildschirm. Der Marienkäfer kann programmiert werden, um in seiner Welt verschiedene Aufgaben zu erledigen. Kleeblätter sammeln, einer Spur von Kleeblättern folgen oder Labyrinthe durchqueren sind einige Beispiele. Die Programme werden grafisch mit der Maus als endliche Automaten erstellt. Eine detaillierte Bedienungsanleitung ist in die Umgebung integriert und erklärt, wie die Welt bearbeitet und Programme erstellt werden.

Karel the Robot wird in einer auf die Bedürfnisse von Anfängern ausgerichteten Mini-Sprache programmiert, die sich an Pascal anlehnt. Karel hat die Idee der Turtle übernommen, aber diskretisiert: Der Roboter lebt in einer einfachen, gitterförmigen Welt. Er kann sich nur in den vier Himmelsrichtungen von Gitterpunkt zu Gitterpunkt bewegen. Zwei Arten von Objekten können in seiner Welt auftreten: Wände zwischen den Gitterpunkten und so genannte 'Beepers' (Piepser), die bei den Gitterpunkten auf dem Boden liegen. Im Gegensatz zur Schildkröte hat Karel Sensoren, mit denen er seine unmittelbare Umgebung wahrnehmen kann. So weiss er, ob es vor ihm eine Wand hat, ob es unter ihm Piepser hat und in welche Richtung er gegenwärtig schaut. Karel trägt einen Sack mit sich, in dem er Piepser sammeln kann, und er versteht Befehle wie move, turnleft, pickbeeper, putbeeper.