臺灣博碩士論文加值系統

本論文的主要目的在於概略地論述與遞迴可數集（recursively enumerable sets）
以及可計算函數（computable functions）相關的一些定理與性質，
同時並將這些定理與性質加以重構或重述。
在第一章中，我們會先針對「可計算」（computable）這個概念作一個簡單的介紹，
並且說明兩種用來定義這個直覺概念的形式化方式。
我會將討論的重點集中在以遞迴的概念來定義何謂可計算函數，
並指出一些與之相關的定理與性質。本章也將介紹遞迴函數的兩個重要觀念:
遞迴可數集以及索引集。
在第二章中，我們會將焦點集中在遞迴可數集以及遞迴理論上面：
首先會進一步介紹另外兩種遞迴可數集的定義方式以及與之相關的基本性質。
接下來將介紹遞迴集合以及有限集合的相關性質。
最後我將會介紹遞迴理論以及其証明，此外還將舉出一些遞迴理論的應用之實例以及其証明。

The main goal of this thesis is to
survey the theorems and properties related
to recursively enumerable function,
and rephrase or reorganize these theorems and properties.
In Chapter one,
I will first explain the concept of ``computable'' in an intuitive way,
and then describe two different formal ways to define computability:
by (partial) recursive functions or by Turing computable functions.
I will look into the recursive function approach and introduce some basic results of it.
Two important relevant concepts,
recursively enumerable sets and index sets will also be introduced in this chapter.
I will then show that several problems are unsolvable.
In chapter two,
I will focus on recursively enumerable sets and the Recursion Theorem.
Two different definitions of recursively enumerable sets
and some basic properties of $r.e.$ sets will be presented.
Then I will show some properties for recursive sets and finite sets.
Finally,
I will present the proof of Recursion Theorem as well as the proofs for
Recursion Theorem with parameters and Recursion Theorem for partial recursive functions.
And then several applications of Recursion Theorem will be given.

摘要------ii
綜論------iii
Abstract---------xiii
Introduction---------1
I. Recursive Functions
1.1 An Intuitive Description
1.2 Some Formal Definition about Computable Functions
1.3 The Basic Results
1.4 Recursively Enumerable Sets and Index Sets
II. Recursively Enumerable Sets and the Recursion Theorem
2.1 Definitions and Basic Properties of Recursively Enumerable Sets
2.2 Properties for Recursive and Finite Sets
2.3 The Recursion Theorem
III. Conclusion
Reference

Soare, Robert I. Recursively Enumerable Sets and
Degrees: A study of Computable Functions and Computably Generated Sets. Springer-Verlag,1987.

Enderton, Herbert B. A mathematical introduction to logic.
Second edition. Harcourt/Academic Press, Burlington, MA, 2001.

Epstein, Richard L. Computability: Computable Functions, Logic, and the Foundations of Mathematics.
Second edition. Wadsworth, 2000.