HackerPapers

arXiv:nlin/0306022nlin.CG

Complexity of Langton's Ant

Anahi Gajardo, Andres Moreira, Eric Goles

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

The virtual ant introduced by C. Langton has an interesting behavior, which has been studied in several contexts. Here we give a construction to calculate any boolean circuit with the trajectory of a single ant. This proves the P-hardness of the system and implies, through the simulation of one dimensional cellular automata and Turing machines, the universality of the ant and the undecidability of some problems associated to it.

arXiv comments
8 pages, 9 figures. Complements at http://www.dim.uchile.cl/~agajardo/langton
Journal reference
Final version in Discrete Applied Mathematics, Vol. 117, Issue 1-3, pp. 41-50 (2002)
DOI
Subjects
nlin.CGCellular Automata and Lattice Gases

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Sep 2020 to Sep 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Why neural networks struggle with the Game of Life 1 comment

    • > the point that dr. Stephen Wolfram has been making for years? Stephen Wolfram, along with many others (predating him): An example. Note the dates. (A New Kind of Science is from 2002.) http://csc.ucdavis.edu/~chaos/Publications/JPC-Publications.... Also see: Chris Langton…

      eternalbanView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.