Aarhus University Seal / Aarhus Universitets segl

Turingmaskiner og logik

Troels Bak Andersen
Lectures for students by students
Friday, 1 March, 2013, at 15:15-16:15, in Aud. D3 (1531-215)
Abstract:
En Turingmaskine er et apparat, der ved hjælpe af en blyant, et viskelæder og en uendelig strimmel papir er i stand til at simulere alverdens algoritmiske beregninger. Jeg vil introducere dette apparat og fortælle hvordan det kan bruges til at snakke om beregnelighed og forhåbentligt ende med at snakke lidt om Gödels ufuldstændighedsætning: Inden for enhver aksiomatisering af regning med de naturlige tal vil der enten være selvmodsigelser eller sande udsagn som ikke kan bevises.
Contact person: Thomas Schmidt