更改

Many problems in mathematics have been shown to be undecidable after these initial examples were established.  In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved (using results of Julia Robinson) Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers. The list of undecidable problems gives additional examples of problems with no computable solution.

Many problems in mathematics have been shown to be undecidable after these initial examples were established.  In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved (using results of Julia Robinson) Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers. The list of undecidable problems gives additional examples of problems with no computable solution.

许多'''<font color="#ff8000">数学 mathematics</font>'''问题在这些初始例子建立之后已被证明是不可判定的。马尔科夫和波斯特在1947年发表的独立论文表明，半群代数字符问题不能有效地判定。推广这个结果，'''<font color="#ff8000">彼得·诺维科夫 Pyotr Novikov</font>'''和'''<font color="#ff8000">威廉·布恩 William Boone</font>'''在1950年代分别证明了'''<font color="#ff8000">群代数字符问题 word problem for groups</font>'''不是有效可解的: 没有给定有限表示'''<font color="#ff8000">群 group</font>'''代数中的一个字符的有效程序，来决定该字符所表示的元素是否是群代数的'''<font color="#ff8000">单位元素 identity element</font>'''。在1970年，'''<font color="#ff8000">尤里·马季亚谢维奇 Yuri Matiyasevich</font>'''使用'''<font color="#ff8000">朱莉娅·罗宾逊 Julia Robinson/font>'''的结果证明了'''<font color="#ff8000">马季亚谢维奇定理 Matiyasevich's theorem</font>''' ，这意味着'''<font color="#ff8000">希尔伯特第十问题 Hilbert's tenth problem</font>'''没有有效的解;该问题提出，是否存在一个有效的程序来决定一个整数上的'''<font color="#ff8000">刁番图方程 Diophantine equation</font>'''有整数解。'''<font color="#ff8000">不可判定问题列表 list of undecidable problems</font>'''提供了更多无法计算的问题的例子。

许多'''<font color="#ff8000">数学 mathematics</font>'''问题在这些初始例子建立之后已被证明是不可判定的。马尔科夫和波斯特在1947年发表的独立论文表明，半群代数字符问题不能有效地判定。推广该结果，'''<font color="#ff8000">彼得·诺维科夫Pyotr Novikov</font>'''和'''<font color="#ff8000">威廉·布恩 William Boone</font>'''在1950年代分别证明了'''<font color="#ff8000">群代数字符问题 word problem for groups</font>'''不是有效可解的: 没有给定有限表示'''<font color="#ff8000">群 group</font>'''代数中的一个字符的有效程序，来决定该字符所表示的元素是否是群代数的'''<font color="#ff8000">单位元素 identity element</font>'''。1970年，'''<font color="#ff8000">尤里·马季亚谢维奇 Yuri Matiyasevich</font>'''使用'''<font color="#ff8000">朱莉娅·罗宾逊 Julia Robinson/font>'''的结果证明了'''<font color="#ff8000">马季亚谢维奇定理 Matiyasevich's theorem</font>''' ，这意味着'''<font color="#ff8000">希尔伯特第十问题 Hilbert's tenth problem</font>'''没有有效的解;该问题提出，是否存在一个有效的程序来决定一个整数上的'''<font color="#ff8000">刁番图方程 Diophantine equation</font>'''有整数解。'''<font color="#ff8000">不可判定问题列表 list of undecidable problems</font>'''提供了更多无法计算的问题的例子。

The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics; the Handbook of Recursive Mathematics (Ershov et al. 1998) covers many of the known results in this field.

The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics; the Handbook of Recursive Mathematics (Ershov et al. 1998) covers many of the known results in this field.

对哪些数学结构可以有效地执行的研究有时被称为'''递归数学'''; 《递归数学手册》（1998）涵盖了这一领域的许多已知成果。

对哪些数学结构可以有效地执行的研究有时被称为'''递归数学''' ; 《递归数学手册》（1998）涵盖了这一领域的许多已知成果。

==Turing computability==

==Turing computability==