臺灣博碩士論文加值系統

摘 要
1900 年，數學家希爾伯特在一場國際數學會議中提出了他著名的二十三個數學問題，本文所要討論的也就是其中的第十問題，亦即：是否存在一個演算法可用以決定任意一個整係數方程式有無整數解？
首先，我們定義一些與丟番圖相關的名詞及其間的關係，同時，我們也要證明一些重要的函數，例如：指數函數，階乘函數都是丟番圖方程式。接著，我們要討論一些常用的邏輯運算符號，如：交集、聯集存在格、所有格在丟番圖型式中所具有的意義。此外，我們還將探討幾個遞迴型式彼此之間及其與丟番圖型式之間的關聯性。
最後我們推導出這些遞迴型式分別等價於可計算函數、可決定關聯、半決定關聯，並據此來證明希爾伯特第十問題是不可解的。

Abstract
In 1900, the great mathematician David Hilbert gave a talk at the International Congress of Mathematicians. In this talk, Hilbert proposed 23 problems. The tenth problem in this list is: Finding an algorithm that, given an arbitrary polynomial
p(x1, . . . , xn) with integer coefficients, decides (YES or NO) whether the polynomial equation p(x1, . . . , xn) = 0 has a solution in integers?
In this paper I will give a survey of the result that
Hilbert’s tenth problem is undecidable. In Chapter 1, I will introduce several concepts related to Diophantine equations (that is, polynomial equations with integer coefficients) and the relationship between them. In Chapter 2 and 3, the exponential function and the factorial function are shown to be Diophantine. Basic logical operation like "or" , "and" , "exist" , and "bounded for all" are discussed in Chapter 1 and 4.
In Chapter 5, I will introduce the concept of recursive enumerability and show that every recursively enumerable relation is Diophantine. In addition, in Chapter 6 we will construct a recursive enumerable relation but it is not recursive.
Finally, Hilbert’s tenth problem is shown to be undecidable.

Contents
1 Basic Definitions 3
2 The Exponential Function Is Diophantine 11
3 Some Important Diophantine Functions 25
4 Bounded For All -Rule 30
5 RE Relation Is Diophantine 35
6 An Example of Nonrecursive RE Relation 41
7 Hilbert’s Tenth Problem Is Unsolvable 50

Bibliography
[1] R.E. Hodel, An Introduction to Mathematical Logic. PWS Publishing Company Press, 1995.
[2] Yuri V. Matiyasevich with a forward by Martin Davis, Hilbert’s Tenth Problem. Cambridge, Massachusetts: MIT Press, 1993.
[3] C. Smorynski, Logical Number Theory I: An Introduction. Berlin, Heidel-berg: Springer-Verlag, 1991.
[4] W. J. LeVeque, Topics in Number Theory vol I. Reading, Massachusetts: Addison-Wesley, 1956.