Bisher habe ich Themen aus den Gebieten der Grundlagen-Informatik, der technischen Informatik, der (hardwarenahen) Programmierung und der Algorithmen besprochen; nicht erwähnt wurde aber (unter anderem) die theoretische Informatik; diesen Missstand möchte ich heute beseitigen und das Wunschthema von Leser Michael beantworten: er hat eine kurze Abhandlung über die Turing-Vollständigkeit erbeten. Nun denn, auf geht’s.