2
$\begingroup$

I came across the (proven) claim that the cellular atomaton "rule $110$" is universal, meaning that it can do every calculation in principle. But to calculate a result, the automaton must "halt" somehow.

How does the automaton "know" when it has to halt, in other words, how is "halting" simulated in this automaton ?

A turing machine has the "halt"-state but "rule $110$" apparently only can manipulate the symbols.

$\endgroup$
-1
$\begingroup$

The 110 never halts. The machine will, for instance, continue forever toward the left filling in $1$'s. So the only stable configuration with finitely many $1$'s (or infinitely many, for that matter) is the configuration with no $1$'s at all.

So my guess is you have to look at a subset of the tape for a specific repeating pattern or something.

$\endgroup$
7
  • $\begingroup$ So, we could fix a specific cell and halt when it is has been filled ? And for the result, this cell has to be ignored ? This would make sense. $\endgroup$
    – Peter
    Jan 23 '18 at 12:54
  • 1
    $\begingroup$ You can't make it that easy, since you don't know beforehand how long the program will run, and therefore you won't know whether the program is finished by the time that specific cell has been filled (at least if you're looking at a cell to the left). But something of the sort, yes, is what I believe you must do. $\endgroup$
    – Arthur
    Jan 23 '18 at 12:55
  • $\begingroup$ If this is allowed , we could also count the number of steps (assuming we already know that after that number of steps the result is reached). What I meant with my comment : If we know that there is a cell filled exactly when the desired result is reached, we could take this for a sign for the automaton to halt. But I do not think that this is always the case. Just to clarify : I am not the downvoter. $\endgroup$
    – Peter
    Jan 23 '18 at 13:21
  • 2
    $\begingroup$ Why the downvote? This seems like a very reasonable answer. If the downvoter thinks it is not, then please explain, so we can all learn something. $\endgroup$
    – Bram28
    Jan 23 '18 at 13:48
  • 1
    $\begingroup$ @Bram28 I also like downvoters to explain why they downvote. Otherwise I will not learn and I will therefore continue as I have done. I am somewhat active on this site, so them not telling me what's wrong will directly affect the quality of this site. Oh well, it's on them I suppose. (If I were to guess, I would say that it is the speculative nature of my last sentence that did it.) $\endgroup$
    – Arthur
    Jan 23 '18 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.