学部・大学院区分
Undergraduate / Graduate

理学部

時間割コード
Registration Code

0613200

科目区分
Course Category

専門基礎科目
Basic Specialized Courses

科目名　【日本語】
Course Title

数学展望Ⅱ

科目名　【英語】
Course Title

Perspectives in Mathematics II

コースナンバリングコード
Course Numbering Code

担当教員　【日本語】
Instructor

GARRIGUE JACQUES ○

担当教員　【英語】
Instructor

GARRIGUE JACQUES ○

単位数
Credits

開講期・開講時間帯
Term / Day / Period

秋水曜日３時限
Fall Wed 3

授業形態
Course style

講義
Lecture

学科・専攻
Department / Program

数理学科

必修・選択
Compulsory / Selected

選択

授業の目的　【日本語】
Goals of the Course(JPN)

この講義では計算と論理の関係を見て行きます。
1930年代にTuringという論理学者が計算の厳密な定義を与え、それによって計算できない関数の存在を示した。
同じ時期に定義された帰納的関数とラムダ計算も同等の性質を持つ。
この重大な結果が数学における証明の完全な自動化を不可能にしており、現在のコンピュータにも影響をしている。

授業の目的　【英語】
Goals of the Course

In this lecture we will study the relation between computation and logic.
In the 1930s, the logicien Alan Turing gave a precise definition of computation, and went on to prove the existence of uncomputable functions.
Recursive function theory and lambda-calculus, discovered in the same period, exhibit the same properties.
This result closed the way to a complete automation of mathematics, and has a large impact on computers.

到達目標　【日本語】
Objectives of the Course(JPN))

* 計算不能問題の存在を理解する
* Church thesis の意味を理解する
* 計算を論理的に記述できる

到達目標　【英語】
Objectives of the Course

* Understand the existence of undecidable problems
* Understand the meaning of the Church thesis
* Be able to describe computation using formal logic

授業の内容や構成
Course Content / Plan

以下の内容を見て行く予定です。

１）Turing機械
Turingが提示した計算のモデル。具体的な計算への応用および計算機との関係も見る。

２）計算不可能な問題
計算ができない問題とその具体的な証明を見る。

３）他の計算モデル
Turing機械と同じ時期に提案されたラムダ計算と帰納的関数という二つの異なる計算モデルを見る。それぞれの計算能力がTuring機械と同等であることが計算可能性の普遍性をいうChurch-Turing提唱の基礎となった。

４）論理学との関係
上記の結果が論理学においてどんな意味を持つのかを見る。

履修条件
Course Prerequisites

履修要件は要さない。

This course will be taught in Japanese.