Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The power of backtracking and the confinement of length


Author: Timothy H. McNicholl
Journal: Proc. Amer. Math. Soc. 141 (2013), 1041-1053
MSC (2010): Primary 03F60, 03D32, 54D05
DOI: https://doi.org/10.1090/S0002-9939-2012-11385-1
Published electronically: August 7, 2012
MathSciNet review: 3003695
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that there is a point on a computable arc that does not belong to any computable rectifiable curve. We also show that there is a point on a computable rectifiable curve with computable length that does not belong to any computable arc.


References [Enhancements On Off] (What's this?)

  • 1. George S. Boolos, John P. Burgess, and Richard C. Jeffrey, Computability and logic, fourth ed., Cambridge University Press, Cambridge, 2002. MR 1898463 (2003a:03001)
  • 2. Vasco Brattka, Plottable real number functions and the computable graph theorem, SIAM J. Comput. 38 (2008), no. 1, 303-328. MR 2399529 (2010b:03083)
  • 3. S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461 (2005h:03001)
  • 4. P.J. Couch, B.D. Daniel, and T.H. McNicholl, Computing space-filling curves, Theory of Computing Systems 50 (2012), no. 2, 370-386. MR 2875304
  • 5. B.D. Daniel and T.H. McNicholl, Effective local connectivity properties, Theory of Computing Systems 50 (2012), no. 4, 621-640.
  • 6. Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288
  • 7. Kenneth Falconer, Fractal geometry, second ed., Mathematical foundations and applications, John Wiley & Sons, Inc., Hoboken, NJ, 2003. MR 2118797 (2006b:28001)
  • 8. Michael R. Garey and David S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. MR 519066 (80g:68056)
  • 9. X. Gu, J. Lutz, and E. Mayordomo, Points on computable curves, Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (Berkeley, CA), IEEE Computer Society Press, October 2006, pp. 469-474.
  • 10. X. Gu, J.H. Lutz, and E. Mayordomo, Curves that must be retraced, Information and Computation 209 (2011), 992-1006. MR 2817185
  • 11. John G. Hocking and Gail S. Young, Topology, second ed., Dover Publications Inc., New York, 1988. MR 1016814 (90h:54001)
  • 12. Peter W. Jones, Rectifiable sets and the traveling salesman problem, Invent. Math. 102 (1990), no. 1, 1-15. MR 1069238 (91i:26016)
  • 13. Ker-I Ko, A polynomial-time computable curve whose interior has a nonrecursive measure, Theoret. Comput. Sci. 145 (1995), no. 1-2, 241-270. MR 1339482 (96j:68094)
  • 14. Jack H. Lutz, The dimensions of individual strings and sequences, Inform. and Comput. 187 (2003), no. 1, 49-79. MR 2018734 (2005k:68099)
  • 15. -, Effective fractal dimensions, MLQ Math. Log. Q. 51 (2005), no. 1, 62-72. MR 2099385 (2006e:68064)
  • 16. J. Miller, Degrees of unsolvability of continuous functions, The Journal of Symbolic Logic 69 (2004), 555-584. MR 2058189 (2005b:03102)
  • 17. R.L. Moore and J.R. Kline, On the most general plane closed point-set through which it is possible to pass a simple continuous arc, Ann. of Math. (2) 20 (1919), no. 3, 218-223. MR 1502556
  • 18. Kate Okikiolu, Characterization of subsets of rectifiable curves in $ {\bf R}^n$, J. London Math. Soc. (2) 46 (1992), no. 2, 336-348. MR 1182488 (93m:28008)
  • 19. Hans Sagan, Space-filling curves, Universitext, Springer-Verlag, New York, 1994. MR 1299533 (95h:00001)
  • 20. R.I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, Berlin, Heidelberg, 1987. MR 882921 (88m:03003)
  • 21. Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. MR 1795407 (2002b:03129)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03F60, 03D32, 54D05

Retrieve articles in all journals with MSC (2010): 03F60, 03D32, 54D05


Additional Information

Timothy H. McNicholl
Affiliation: Department of Mathematics, Lamar University, Beaumont, Texas 77710
Address at time of publication: Department of Mathematics, Iowa State University, Ames, Iowa 50011
Email: McNichol@iastate.edu

DOI: https://doi.org/10.1090/S0002-9939-2012-11385-1
Received by editor(s): April 5, 2011
Received by editor(s) in revised form: August 2, 2011, and August 4, 2011
Published electronically: August 7, 2012
Communicated by: Julia Knight
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society