PHV444en Proof, Meaning, Computation

Faculty of Arts
Autumn 2024
Extent and Intensity
2/0/0. 4 credit(s). Type of Completion: k (colloquium).
In-person direct teaching
Teacher(s)
prof. PhDr. BcA. Jiří Raclavský, Ph.D. (lecturer)
Guaranteed by
prof. PhDr. BcA. Jiří Raclavský, Ph.D.
Department of Philosophy – Faculty of Arts
Supplier department: Department of Philosophy – Faculty of Arts
Timetable
each odd Thursday 12:00–13:40 A11, except Mon 18. 11. to Sun 24. 11.
Prerequisites
PHBP Proseminar
The student should know the basics of first-order logic (FOL) and Gödel’s incompleteness results, or keep up to it during the course.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
Selected topics mainly from logic on the borderline of computer science, philosophy, mathematics, AI, and even formal linguistics. The aim is to gather essential knowledge from the rich area of the PHILOSOPHY OF COMPUTER SCIENCE and PHILOSOPHY OF COMPUTING. It overlaps even with the COMPUTATIONAL PHILOSOPHY and it is a part of the PHILOSOPHY OF TECHNOLOGY.
Learning outcomes
(a) knowledge of some foundational issues of (mathematical) logic, computation, AI;
(b) logical reasoning;
(c) methods of formal reasoning;
(d) analytical and algorithmic thinking;
(e) methods of knowledge representation;
Syllabus
  • Algorithms, Turing Machines
  • Computable Functions, Church-Turing Thesis
  • Decidability, the Halting Problem
  • Incompleteness, the Lucas-Penrose Argument
  • Sequent Calculus/Natural Deduction, the Curry-Howard Correspondence
  • Foundations of AI
Literature
    recommended literature
  • Stanford Encyclopedia of Philosophy (SEP) logic, mathematic and computer science entries (e.g. Turing Machines, Recursive Functions, Computability and Complexity, Automated Reasoning, Logic-based Artificial Intelligence)
  • Stanford Encyclopedia of Philosophy (SEP) philosophy and history entries (e.g. The Philosophy of Computer Science, Computational Philosophy, Hilbert's Program, Computational Theory of Mind, ...)
  • RAPAPORT, WIlliam C.. Philosophy of Computer Science: An Introduction to the Issues and the Literature. Willey-Blackwell. 2023.
    not specified
  • RUSSELL, Stuart J. and Peter NORVIG. Artificial intelligence : a modern approach. Fourth edition. Hoboken: Pearson, 2021, xvii, 1115. ISBN 9780134610993. info
  • RUSSELL, Stuart. Human Compatible. Praha: Argo, 2021. info
  • RUSSELL, Stuart J. Jako člověk : umělá inteligence a problém jejího ovládání. Translated by Jiří Zlatuška. První vydání v českém j. Praha: Argo, 2021, 271 stran. ISBN 9788025736418. info
  • MIMRAM, Samuel. Program: proof. [Velká Británie]: [nakladatel není známý], 2020, 539 stran. ISBN 9798615591839. info
  • SIPSER, Michael. Introduction to the theory of computation. 3rd ed. [S.l.]: Cengage Learning, 2013, xxii, 458. ISBN 9781133187813. info
  • PUDLÁK, Pavel. Logical foundations of mathematics and computational complexity : a gentle introduction. 1st edition. Cham: Springer, 2013, xiv, 695. ISBN 9783319342689. info
  • HODGES, Andrew. Alan Turing : the enigma. Edited by Douglas R. Hofstadter. Centenary ed. Oxford: Princeton University Press, 2012, xxxi, 586. ISBN 9780691155647. info
  • HOFSTADTER, Douglas R. Gödel, Escher, Bach : existenciální gordická balada : metaforická fuga o mysli a strojích v duchu Lewise Carrolla. Translated by Petr Holčák. 1. vyd. v českém jazyce. Praha: Dokořán, 2012, 830 s. ISBN 9788073632656. info
  • The undecidable : basic papers on undecidable propositions, unsolvable problems, and computable functions. Edited by Martin Davis. 1st pub. Mineola, New York: Dover Publications, 2004, 413 s. ISBN 0486432289. info
  • HOPCROFT, John E., Rajeev MOTWANI and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. 2nd ed. Boston: Addison-Wesley, 2001, xiv., 521. ISBN 0201441241. info
  • HOFSTADTER, Douglas R. Gödel, Escher, Bach : an eternal golden braid. 20th-anniversary ed. London: Penguin Books, 2000, xlv, 777. ISBN 0140289208. info
  • GIRARD, Jean-Yves, Paul TAYLOR and Yves LAFONT. Proofs and types. Cambridge: Cambridge University Press, 1990, xi, 176. ISBN 0521371813. info
  • BOOLOS, George. Computability and logic. Edited by Richard C. Jeffrey. 3rd ed. Cambridge: Cambridge University Press, 1989, x, 304. ISBN 0521389232. info
Teaching methods
Lectures with presentations (etc.), discussions, homeworks. Use of e-learning in IS.
LECTURES:
Each lecture contains:
  • (i) PDF presentation;
  • (ii) external texts;
  • (iii) external software, videos etc.
  • (iv) presentation based on a self-studied book.
    HOMEWORKS:
    Each lecture requires:
  • (i) self-study of external texts and other materials on the lecture topics;
  • (ii) fulfilling homework (as e-test, ROPOT) on lecture topic;
  • (iii) self-study of the external book not on the lecture topics;
  • (iv) preparing a presentation based on the self-studied book.
    • Assessment methods
  • (i) homeworks via e-learning
  • (ii) activities (attendance among them)
  • both from which one needs a certain minimal number of points
  • as a colloquial 'repetition', there will be (iii) an e-test.
    • Náhradní absolvování
    Combined students (students on foreign stay, long-termed ill, ...): contact the teacher for details and agreement, self-study of materials from Interactive syllabi, and filling regular homeworks. Attendance to classes brings surplus points, but the minimum required points can be gathered without attendance from homeworks. But for colloquial exam (= presentation of projects), attendance is typically required.
    Language of instruction
    Czech
    Study support
    https://is.muni.cz/auth/el/phil/podzim2024/PHV444en/index.qwarp
    Further comments (probably available only in Czech)
    Study Materials
    General note: Předmět je vyučován v angličtině.
    • Enrolment Statistics (recent)
    • Permalink: https://is.muni.cz/course/phil/autumn2024/PHV444en