23
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Cellular Automata are Generic

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Any algorithm (in the sense of Gurevich's abstract-state-machine axiomatization of classical algorithms) operating over any arbitrary unordered domain can be simulated by a dynamic cellular automaton, that is, by a pattern-directed cellular automaton with unconstrained topology and with the power to create new cells. The advantage is that the latter is closer to physical reality. The overhead of our simulation is quadratic.

          Related collections

          Most cited references15

          • Record: found
          • Abstract: found
          • Article: not found

          Trial and error predicates and the solution to a problem of Mostowski

          The purpose of this paper is to present two groups of results which have turned out to have a surprisingly close interconnection. The first two results (Theorems 1 and 2) were inspired by the following question: we know what sets are “decidable” — namely, the recursive sets (according to Church's Thesis). But what happens if we modify the notion of a decision procedure by (1) allowing the procedure to “change its mind” any finite number of times (in terms of Turing Machines: we visualize the machine as being given an integer (or an n-tuple of integers) as input. The machine then “prints out” a finite sequence of “yesses” and “nos”. The last “yes” or “no” is always to be the correct answer.); and (2) we give up the requirement that it be possible to tell (effectively) if the computation has terminated? I.e., if the machine has most recently printed “yes”, then we know that the integer put in as input must be in the set unless the machine is going to change its mind; but we have no procedure for telling whether the machine will change its mind or not.
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Sequential abstract-state machines capture sequential algorithms

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              TERM GRAPH REWRITING

              D. PLUMP (1999)
                Bookmark

                Author and article information

                Journal
                2015-04-12
                Article
                10.4204/EPTCS.179.2
                1504.03013
                461d7c4a-b7a7-4323-9d16-8c36c617294a

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                EPTCS 179, 2015, pp. 17-32
                In Proceedings DCM 2014, arXiv:1504.01927
                cs.LO
                EPTCS

                Theoretical computer science
                Theoretical computer science

                Comments

                Comment on this article