date: 2024-11-17
title: 01-TOC-Intro
status: DONE
author:
  - AllenYGY
tags:
  - NOTE
  - TOC
descriptions: "Theory Of Computation Introduction---A brief introduction to the history of mathematical logic and computer science."	
publish: True

TOC-Intro

Computation Definition

A computation is a procedure to calculate the desired output of a computational problem.

If only solve decision problems, a computation is a procedure to decide whether an element is in a set or not.

History

Gottfried Wilhelm Leibniz 1646-1716

Calculus ratiocinator: a theoretical universal logical calculation framework
Characteristica universalis: a universal conceptual language

Gottlob Frege 1848-1925

Begriffsschrift: (concept-script)
- First book on symbolic logical
- To implement calculus ratiocinator

Kurt Gödel 1906–1978

Incompleteness theorem: if an axiom system contains natural numbers, then
1. there is a proposition which is unprovable;
2. and it cannot prove its consistency.
Sabota g ed Hilbert’s program

Alonzo Church 1903-1995

Lambda calculus

Alan Turing 1912-1954

Turing machine

这段历史概述了数学逻辑与计算机科学发展的几个关键人物及其贡献，涉及从17世纪到20世纪的重要理论基础。这些贡献共同构建了现代逻辑学、数学以及计算机科学的基础，以下是逐步的介绍：

1. Gottfried Wilhelm Leibniz (1646-1716)

莱布尼茨是一位德国哲学家、数学家，被认为是现代数学逻辑的奠基人之一。他的两项核心构想对后来的逻辑发展产生了深远影响：

Calculus ratiocinator（理性演算器）：一个假设性的通用逻辑计算框架，旨在通过数学和逻辑计算解决一切问题。
Characteristica universalis（通用特征语言）：一种理想化的通用概念语言，试图以形式化的方式表达所有知识。这是莱布尼茨对人类知识进行逻辑编码的梦想，也是后来形式逻辑的前身。

尽管莱布尼茨的构想在他在世时未能实现，但它为后来的逻辑学家提供了启发。

2. Gottlob Frege (1848-1925)

弗雷格是德国逻辑学家，被称为现代逻辑学的奠基人之一。他的主要贡献体现在：

Begriffsschrift（概念文字）：这是第一本关于符号逻辑的书，首次提出了一种形式化的逻辑语言，用以表达数学和逻辑推理。这一理论直接落实了莱布尼茨“理性演算器”的思想，是现代形式逻辑的起点。
他还发展了谓词逻辑，为数学基础提供了更加严谨的框架。

弗雷格的工作直接影响了后来的逻辑学家，包括罗素和维特根斯坦。

3. Kurt Gödel (1906–1978)

哥德尔是奥地利逻辑学家，以他的不完备性定理闻名，该定理对数学和逻辑的基础提出了深刻的限制：

不完备性定理指出：在任何包含自然数的公理系统中：
1. 存在一个无法被证明也无法被否定的命题（即“不可判定命题”）。
2. 这个系统无法证明自身的相容性。
哥德尔的工作揭示了数学体系的固有局限性，破坏了希尔伯特“证明数学一致性”的乐观计划（Sabotaged Hilbert’s program）。

哥德尔的理论对数理逻辑和理论计算机科学产生了重大影响。

4. Alonzo Church (1903-1995)

丘奇是美国数学家，他的λ演算（Lambda Calculus）为计算理论奠定了重要基础：

λ演算是一种数学形式系统，用以研究函数定义和计算过程。它与图灵机被认为是等价的，提供了描述计算过程的一种抽象方法。
丘奇证明了一些问题在形式系统中是不可判定的，这与哥德尔的结果相辅相成。

λ演算后来成为编程语言理论的重要基础。

5. Alan Turing (1912-1954)

图灵是英国数学家、逻辑学家，被誉为计算机科学之父。他的贡献主要包括：

图灵机：一种假想的计算设备，旨在模拟任何可计算过程。这一模型定义了“可计算性”的概念，被认为是现代计算机的理论基础。
图灵与哥德尔、丘奇的研究共同确立了计算理论的基本框架。

图灵还提出了“图灵测试”，作为人工智能的早期概念。