3
$\begingroup$

Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial state the next state in the evolution. Only then did I realise that this is an obviously finite process (because it's a primitive recursive function, I suppose?).

So my question is: what, involving Rule 110, would one have to simulate to prove Turing-completeness of some formalism? I thought initially a function that takes a predicate and an initial state and then evaluates new states until the predicate holds might suffice, but I am not so sure how that translates into the notion of termination of Turing machines. Or maybe I'm just generally way off.

  • 0
    I don't know the answer myself, but I see that [the Wikipedia article on Rule 110](http://en.wikipedia.org/wiki/Rule_110) has [a section titled "proof of universality"](http://en.wikipedia.org/wiki/Rule_110#The_proof_of_universality). Have you looked at that?2012-08-09
  • 0
    I have, but it's a bit too complicated for me and seems to go deeper into the details of the proof than I need for my question. The sentence "The function of the universal machine in Rule 110 requires an infinite number of localized patterns to be embedded within an infinitely repeating background pattern." jumps out -- it just so happens that the language I was using, Haskell, supports infinite data structures, but they need to be (obviously) computable infinite data structures, and I'm not sure if that's what the proof uses.2012-08-10

1 Answers 1