{"id":288,"date":"2021-01-23T15:10:37","date_gmt":"2021-01-23T15:10:37","guid":{"rendered":"http:\/\/www.peter-zaspel.de\/?page_id=288"},"modified":"2026-07-13T06:37:40","modified_gmt":"2026-07-13T06:37:40","slug":"automata-computability-and-complexity-spring-2021","status":"publish","type":"page","link":"https:\/\/www.peter-zaspel.de\/?page_id=288","title":{"rendered":"Automata, Computability and Complexity"},"content":{"rendered":"\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/moodle.jacobs-university.de\/pluginfile.php\/34318\/mod_label\/intro\/wordcloud.png\" alt=\"\"\/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Course Description<\/h2>\n\n\n\n<p>This module introduces the mathematical theory of computation. Several types of abstract computational machines (called automata) are introduced together with the associated theory of formal languages. A formal language is a set of words over a defined alphabet that are well-formed according to a specific set of rules, called the grammar of the language. After studying the relationship between automata models and classes of formal languages, this course addresses the fundamental question &#8220;What problems can a computer possibly solve?&#8221; by characterizing those solvable problems, equivalently, through Turing machines, random access machines, recursive functions and lambda calculus. A full answer to the related question, &#8220;How much computational resources are needed for solving a given problem?&#8221; is not known today. However, the basic outlines of today&#8217;s theory of computational complexity will be presented up to the most famous open problem in computer science, namely the &#8220;P = NP&#8221; question: if a computer could guess the right answer to a computational problem (and only needs to check its correctness), would that computer be faster than another one that cannot guess the right solution? This may seem a ridiculously obvious case of a clear YES answer, but in fact it is considered by many to be the deepest open question in contemporary mathematics (and computer science, of course).<br><br>This module provides the core education in theoretical computer science. The material covered in this module gives students access to any field in computer science, which is based on discrete-mathematical formal foundations, such as the theory of automata and formal languages or compiler design.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Course literature<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Michael Sipser: Introduction to the Theory of Computation,2nd edition, PWS Publishing Company, 1997. (Primary Literature).<\/li>\n\n\n\n<li>John Hopcroft, Rajeev Motwani, Jeffrey Ullman: Introduction toAutomata Theory, Languages, And Computation, 3rd edition, Pearson, 2006.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Syllabus<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Introduction to Mathematics<\/li>\n\n\n\n<li>Regular Languages<\/li>\n\n\n\n<li>Context-free languages<\/li>\n\n\n\n<li>Turing machines<\/li>\n\n\n\n<li>Decidability <\/li>\n\n\n\n<li>Complexiity<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Course Description This module introduces the mathematical theory of computation. Several types of abstract computational machines (called automata) are introduced together with the associated theory of formal languages. A formal language is a set of words over a defined alphabet<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":20,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","_mc_calendar":[],"footnotes":""},"class_list":["post-288","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/pages\/288","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=288"}],"version-history":[{"count":5,"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/pages\/288\/revisions"}],"predecessor-version":[{"id":1765,"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/pages\/288\/revisions\/1765"}],"up":[{"embeddable":true,"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=\/wp\/v2\/pages\/20"}],"wp:attachment":[{"href":"https:\/\/www.peter-zaspel.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=288"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}