Discussion on question by paulpaul1076: Is the halting problem decidable for 3 symbol one dimensional cellular automata?

D.W.

01:12

Can you edit the question to add one concrete example of a specific cellular automaton where you don't know how to solve the halting problem? To specify a cellular automaton, you'll need to give 27 rules (i.e., for each possible triple of symbols, you'll need to give us a rule for what happens for that triple).

paulpaul1076

07:41

@r.e.s. i think you are exploring unnecessary details. uncomputable word are uncomputable, because the function that computes them never halts. but ok, consider them to be finite, sure.

@D.W. yes, in a moment

paulpaul1076

08:02

@D.W. why did you edit my question writing that the input is state s, if the input is some word?

D.W.

@paulpaul1076, What distinction between state vs word did you have in mind? I thought they're the same thing. Have I misunderstood something?

If I've misunderstood, I apologize. It was a good-faith attempt to clarify the question, but if I erred somehow, I apologize -- let's fix it!

paulpaul1076

@D.W. the thing is that I can give as input the word w1 and the automaton might halt on that word at some point, because the word itself might be structured in a way that regard of us having those non-halting rules 00x->y we might never get to them, but it can also run forever if i give another word that leads us to using those rules. Is that clear? Or did I not explain it well again?

regardless of*

Maybe I don't understand what you mean by state.

To me the word state means some state of the system after several steps. But maybe you meant the same thing

Sorry, maybe you are right

if it's just a word written on the first level of our grid, then it is indeed the same thing.

D.W.

Sorry, you lost me there. Not sure how to help at this point, I'm afraid....

paulpaul1076

Well, we write a word on the first level of our grid. To me that's what the first state is. The on the second level we have a word in the second state, after we used the derivation rules and wrote it there, get it? That's how I understand the word "state"

let's consider a binary CA and the only rules that produce a '1' are 001->1 and 100->1, the others produce '0'

then in the first state our word is

(let's say the input word is "1")

in the first state it's just .....1.....

in the second state it's .....101.....

then it's .....10001....

etc

the word expands, but maybe by "state" you mean the state of the system

@D.W. What's unclear to me after that, is the question "Has the automaton halted in state s?", because we provide that state as input, and obviously the word might transform many more states before reaching the dead state. Maybe you should clarify by what state means

transform into*

user148606

09:55

The proof for the 2-symbol case is not convincing. First if the rule is ***-> 1 then it is halting according to your definition contrary to what you say in the first part. Second your argument about waiting 2^n steps doesn't seem to use the fact that there are only 2 states or a radius-1 neighborhood. Why can't you wait 3^n steps for the 3-states case?

paulpaul1076

@user148606 try maybe doing this on paper? Because what you said doesn't really make any sense. We do 2^n steps, because there are 2^n words of size n that can have either a 0 or a 1 for each letter, but we can only do this if the word does not expand, because in that case it becomes similar to linear bounded automaton. 3^n steps for the 3-state case? What 3 state case? 3 symbol case? Once again, the word might expand! And that n of yours will be changing

user148606

sorry, I mean 3-symbol case. Where do you really use the fact that there are 2 symbols.

paulpaul1076

10:10

what fact that there are 2 symbols? I'm sorry, I don't understand your question

user148606

10:36

Ok, sorry for the confusion, I finally got your argument: if you don't expand then it's easy to decide and if you expand (left or right) it cannot halt. The point is that for elementary CA, deciding expansion is easy because it depends only on transitions 100 and 001. Still if you have transitions 000->1 and 111->1, there's an argument to give: the background of 0s is turned into 1s and now halting means that you reach some state whose 0s will never disappear.

paulpaul1076

rules 000->1 and 111->1 will make your entire grid black and the automaton won't halt, because the process will go on forever

by halt i mean "die", like the death of a system in the conway's game of life, we can't produce any more non-white cells in the future states

user148606

By halt youmean that you reach a fixed point with a finite number of 1s, right? Because your definition doesn't say this.

paulpaul1076

no, reach a state s where we have all zeros on tape, from which we can't reach a state t, where you have anymore ones on tape.

that's for the binary CA

for the ternary CA, we also can't produce anymore twos

user148606

So a state with 1s everywhere and just a finite number of 0 that will never disappear is OK?

paulpaul1076

11:03

If you have don't have rules 001->1, 100->1 and 000->1 in binary CA, and do 2^n steps, after which the automaton does not halt, it means that it has gotten into periodic behavior, it means that that periodic behavior will go on forever and the automaton will not halt, because state A produces state B and state B produces state A.

I don't understand what you mean by "is OK?"

user148606

What is the definition of halting ? If I read what you wrote, then a configuration with all 1s except a finite number of Os such that these 0s are never turned into 1s in the future is a halting configuration.

paulpaul1076

Do you understand what I mean by "tape"?

user148606

Yes

paulpaul1076

Okay, so, if at some state, after doing a certain number of steps, we have an empty tape with no non-white cells, and in all the future states we have the same tape, then the automaton has halted.

user148606

OK

paulpaul1076

11:13

the automaton is not able to produce anymore non-white cells in the future states, for short.

user148606

Ok, ok, it's just an example. Give me a definition.

paulpaul1076

the definition is in my post

user148606

11:25

take F = 000->1, 111->1, and x->x else. Then F halts for any input, right?

I meant: x->x else

paulpaul1076

what is x->x?

is this for binary CA? If so, then no, it doesn't, you will always have 1's

user148606

Fuck ,x, - > x

There is text formatting that removes stars or underscores...

I mean that a cell which sees Os and 1s stays unchanged

paulpaul1076

you do realize that your x->x rules will never be triggered in places where we have all zeros, because those will be transformed into all ones, and the only rule that will be triggered in those places is 111->1

so the system will never halt

user148606

Please, re-read your definition : you say s(i) = 0 implies t(i) = 0 for any future state t. So when s(i) = 1 there is no constraint at all

paulpaul1076

what constraint?

the tape is infinite!

all the symbols in state s are 0, which means that if the automaton has halted, in any state t, that comes after s, we will also have all zeros, and that's what the definition says

You can think of this as periodic behavior which produces one all-zeros tape after the other (this is what halting means).

user148606

12:20

Suppose s is such that s(0) = 0 and s(i) = 1 for i<>0. Suppose that F(s) = s (you CA doesn't change s). Then your definition of halting apply.

paulpaul1076

do you still not understand something i wrote or what?

user148606

12:38

I understand everything you wrote. I'm just saying that with your current definition of halting, your proof for elementary CA is not convincing. But I give up, that's not so important, and everything is OK if we take the following definition of halting: reaching a fixed point with a finite number of 1s.

"finite number of non-zero symbols"

paulpaul1076

I think you are trolling, so I'm going to stop responding.

user148606

12:58

Keep cool. I was just trying to clarify what you mean because you contradicted your formal definition. Have a good day and tell us when you have an answer for the 3-symbols case.

r.e.s.

14:12

Have you read Wolfram's paper "Computation Theory of Cellular Automata"? (You can Google it.) It discusses some undecidable properties for his "class 4" CA (e.g. Rule 110). I could be mistaken, but the following quote (p. 52) seems contrary to your claims: "In a class 4 cellular automaton, evolution from an initial configuration of size
no may yield arbitrarily large configurations, but then ultimately contract to give a
size n configuration. No upper bound on the time or memory space required to

paulpaul1076

@r.e.s. size n configuration can crawl to the left, like so:

0000111111000
0001111110000
0011111100000

it is size n, but it is not static

i don't care about any finite configurations, i only care about a configuration with all zeros from which no non-zero configuration can be derived! and that's when the automaton halts, in other cases it does not

i seriously can't understand how after so much time of explaining some of you still can't see what i am saying

r.e.s.

14:39

You said "i only care about a configuration with all zeros from which no non-zero configuration can be derived!" A configuration with all zeroes is a finite ("empty") configuration, so the Wolfram quote seems to imply that its reachability by a "class 4" CA (e.g. Rule 110) is undecidable, irrespective of what configurations it may evolve into.

paulpaul1076

@r.e.s. Did you read my post at all?

CA Rule 110 includes derivation rule 001->1

with that rule there will always be at least one '1' on the tape in the next state.

it will do this:

00000000001....
0000000001......
000000001........
00000001..........

etc..

r.e.s.

OK, so I picked the wrong example -- but what about all the other binary "class 4" CA?

paulpaul1076

i proved that it is decidable for binary CA, what more do you need?

Transcript for

Discussion on question by paulpaul107…