关于强迫折返的可计算曲线

平面曲线是指单位闭区间在连续函数映射下的影像。这样的函数叫做曲线的参数化。如果一条曲线有一个单调的参数化函数，该曲线是简单曲线。如果一条曲线有可计算的参数化函数，则相应的曲线是可计算的。Gu、LutzHMayordomo最近证明了，有些可计算的简单曲线没有可计算的参数化函数。这样的曲线叫做强迫折返的。本文探讨的是强迫折返的次数对曲线复杂性的影响。

On the Forced Retracing Computable Curves

A planar curve can be defined as the image of the unit interval under a continuous function which is so-called parametrizafion of the curve. The curves parameterized by injective continuous functions are called simple. If a curve has a computable parametrization, then it is called computable. Surprisingly, Gu, Lutz and Mayordomo show in 4] that there exists a computable simple curve which does not have any injective computable parametrization. That is, the computable parametrization of this curve must retrace the curve. In this paper, we first introduce different classes of computable curves according to the number of retracing allowed in a computable parametrization, then we show an infinite proper hierarchy of these classes. Therefore, the retracing number allowed in the computable parametrization can be used to measure the complexity of a computable curve.