Is Colorized life more powerful than life computationally?
Is Colorized life more powerful than life computationally?
hi everybody.
it seems to me we can use color to solve the halting problem
for example we can use green glider to signal "halt" and red glider to signal "does not halt"
because life patterns have the same behavior regardless of colors no counter example can be constructed
so halting problem is logically an open question for colorized life
do you share this intuition ?
it seems to me we can use color to solve the halting problem
for example we can use green glider to signal "halt" and red glider to signal "does not halt"
because life patterns have the same behavior regardless of colors no counter example can be constructed
so halting problem is logically an open question for colorized life
do you share this intuition ?
Re: Is Colorized life more powerful than life computationally?
noraoofha wrote: ↑June 2nd, 2023, 2:39 amhi everybody.
it seems to me we can use color to solve the halting problem
for example we can use green glider to signal "halt" and red glider to signal "does not halt"
because life patterns have the same behavior regardless of colors no counter example can be constructed
so halting problem is logically an open question for colorized life
do you share this intuition ?
Re: Is Colorized life more powerful than life computationally?
To clarify this answer, I assume that raoofha asked if multicolor Life is “more computationally powerful” than normal B3/S23. No, colorful Life is not more Turing-complete than Life (I don’t even understand how something might be more computationally universal than some other thing). You (raoofha) said that this might be the solution to the halting problem by using different-color gliders for indication if the Turing machine halts or not. This still doesn’t solve the problem of finding the general halting-problem solving algorithm, which we know that doesn’t exist. You proposed a method of the solution output, but not the algorithm. We could do the same in normal Life.galoomba wrote: ↑June 2nd, 2023, 7:21 amnoraoofha wrote: ↑June 2nd, 2023, 2:39 amhi everybody.
it seems to me we can use color to solve the halting problem
for example we can use green glider to signal "halt" and red glider to signal "does not halt"
because life patterns have the same behavior regardless of colors no counter example can be constructed
so halting problem is logically an open question for colorized life
do you share this intuition ?
Last edited by b3s23love on June 2nd, 2023, 7:39 am, edited 1 time in total.
Support Conway's Story Mode!
- confocaloid
- Posts: 5565
- Joined: February 8th, 2022, 3:15 pm
- Location: learn to protect yourself against stray gliders and sparks and self-destruct mechanisms
Re: Is Colorized life more powerful than life computationally?
Forum Rules wrote: ↑3. In order to keep the forums organized, please: (...)
d. Quoting earlier posts is fine (and encouraged), but only quote text that is actually relevant to your post.
4. This is an academic forum, not a chat or microblogging platform. (...)
127:1 B3/S234c User:Confocal/R (isotropic CA, incomplete)
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Re: Is Colorized life more powerful than life computationally?
I never said that I solved the halting problem, I conjectured that there is a colored life that solves the halting problem, and we can't do that in colorless life because without colors there is no way to distinguish two different answersb3s23love wrote: ↑June 2nd, 2023, 7:34 amYou (raoofha) said that this might be the solution to the halting problem by using different-color gliders for indication if the Turing machine halts or not. This still doesn’t solve the problem of finding the general halting-problem solving algorithm, which we know that doesn’t exist. You proposed a method of the solution output, but not the algorithm. We could do the same in normal Life.
Re: Is Colorized life more powerful than life computationally?
I didn't say that you solved the halting problem, but you said that there might be a colored life pattern that solves the halting problem. No, the halting problem is undecidable either way. Regarding the output differentiation, you could do the same in regular Life by using two glider lanes for outputs. You don't need different-color gliders.raoofha wrote: ↑June 2nd, 2023, 7:58 amI never said that I solved the halting problem, I conjectured that there is a colored life that solves the halting problem, and we can't do that in colorless life because without colors there is no way to distinguish two different answersb3s23love wrote: ↑June 2nd, 2023, 7:34 amYou (raoofha) said that this might be the solution to the halting problem by using different-color gliders for indication if the Turing machine halts or not. This still doesn’t solve the problem of finding the general halting-problem solving algorithm, which we know that doesn’t exist. You proposed a method of the solution output, but not the algorithm. We could do the same in normal Life.
Last edited by b3s23love on June 2nd, 2023, 1:17 pm, edited 1 time in total.
Support Conway's Story Mode!
Re: Is Colorized life more powerful than life computationally?
it you define the halting problem as normally defined
h(m)=1 if turing machine m halts
h(m)=0 if turing machine m does not halt
then it can be easily diagonalized by a life pattern equivalent to the following
g()=if h(g) then g()
but if you define it like this
h(m)=1 in green if turing machine m halts
h(m)=1 in red if turing machine m does not halt
then there is no obvious diagonalization
Re: Is Colorized life more powerful than life computationally?
What do you mean by diagonalization?
Support Conway's Story Mode!
Re: Is Colorized life more powerful than life computationally?
It can't output a red glider if it doesn't halt, as outputting that glider would be halting.
User:HotdogPi/My discoveries
Periods discovered:
All evens up to 128 except 52,58,78,82,92,94,98,104,118,122
5-15,㉕-㉛,㉟㊺,51,63,65,73,75
1㊳㊵㊹㊼㊽,54,56,72,74,80,90,92
217,240,300,486,576
Guns: 20,21,32,54,55,57,114,117,124,126
SKOPs: 32,74,76,102,196
Periods discovered:
All evens up to 128 except 52,58,78,82,92,94,98,104,118,122
5-15,㉕-㉛,㉟㊺,51,63,65,73,75
1㊳㊵㊹㊼㊽,54,56,72,74,80,90,92
217,240,300,486,576
Guns: 20,21,32,54,55,57,114,117,124,126
SKOPs: 32,74,76,102,196
Re: Is Colorized life more powerful than life computationally?
diagonalization is a method of proof in mathematics and computer science to show that the halting problem is undecidable, but if you can not use diagonalization like in colored life then halting problem is an open question for colored life in my opinion.
Re: Is Colorized life more powerful than life computationally?
you mean for itself? like "h(h)". it can not output a green glider for itself but it can output a red glider for itself because that is a correct answer, "h" will keep outputing gliders so "h(h)=1 in red"
Re: Is Colorized life more powerful than life computationally?
You can emulate coloured life with a Turing machine though, so it reduces to the proof of undecidability for Turing machines.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
no it does not reduce to the proof of undecidability for turing machine because you can emulate turing machine in colored life

Re: Is Colorized life more powerful than life computationally?
We can define a partial order <= on computational models, where we say A <= B if A can be emulated in B. You said Turing machines <= colored life, and colored Life <= Turing machines, so these are in fact equivalent. In fact, if A <= B and B <= A, we may call A and B equivalent, and the Turing-complete computational models are precisely those equivalent to Turing machines (assuming the Church-Turing thesis). Any computational model that is Turing-complete (e.g. lambda calculus and Life) may be used instead, so you don't have to "prefer" any specific one.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
Re: Is Colorized life more powerful than life computationally?
I don't know how you can do that can you give me a reference to look for?pzq_alex wrote: ↑June 2nd, 2023, 11:25 amWe can define a partial order <= on computational models, where we say A <= B if A can be emulated in B. You said Turing machines <= colored life, and colored Life <= Turing machines, so these are in fact equivalent. In fact, if A <= B and B <= A, we may call A and B equivalent, and the Turing-complete computational models are precisely those equivalent to Turing machines (assuming the Church-Turing thesis). Any computational model that is Turing-complete (e.g. lambda calculus and Life) may be used instead, so you don't have to "prefer" any specific one.
if I enumerate the set of turing machine by T_i
and the set of colored life by C_i
such that T_i is equivalent to C_i
and if P=T_k is a partial solution to the halting problem
and G is a counter example for P such that P(G) does not halt and G does not halt
and if H=C_k is a solution to the halting problem that I claim to exist
then H(G)=1 in red (the Gth glider that H output is red)
notice that P and H are equivalent
so my point is that there is no contradiction in believing that H exist
Re: Is Colorized life more powerful than life computationally?
They have the same behavior within the CA, i.e. you cannot internally distinguish them. But you can distinguish them externally, because they're different states.
Suppose colorized life solved the halting problem in this manner, then you can just emulate it with a turing machine that checks the color of a glider on an output lane.
The explicit proof this doesn't solve the halting problem (exactly a subcase of the normal one): Suppose colorized life solved the halting problem in this way. Build, then, a construction that checks if a turing machine passed its own source code halts, and outputs a red glider if no halt and green if halt. Since colorized life is completely defined by its computable transitions, emulate this whole machine, including input, with a turing machine, but have the turing machine check the color of the output glider. It can do this because it's quite trivial to check the state of a given cell: just, when it stops being empty, check if green or red. Now make this turing machine halt only if it sees a red glider.
Input this turing machine's entire source code into the turing machine itself, now it passes into the colorized computer. If it halts, it doesn't halt, and if it doesn't halt, it does. Contradiction, so colorized life doesn't solve the halting problem.
not active here but active on discord
κ is weakly mahlo iff the set of regulars less than κ is stationary in κ.
κ is weakly mahlo iff the set of regulars less than κ is stationary in κ.
Re: Is Colorized life more powerful than life computationally?
you didn't read my last comment. you're proof does not work
suppose P is a turing machine that tries to solves the halting problem
now consider G your counter example for correctness of P, now P is very clever if you try to deceive it, it does not halt
so P(G) does not halt and G also does not halt because it calls P
now consider when we translate P to colored life pattern, let's call that H
and now when you run H, it keeps outputing glider in two different color, green and red depending on whether nth turing machine halts or does not halt
as far as H is concerned P does not need to halt on any of it's input
P only need to be special in such a way that when you translate it to colored life it solves the halting problem without contradiction
Re: Is Colorized life more powerful than life computationally?
please tell me what the error in my proof is, then. As far as I can tell your post just provided an example of the construction I provided in my proof... called on a different turing machine, and, wow! If you don't do the construction of the counterexample right, it's not a counterexample! Magic!!!
Yes, if you call my construction on something that isn't actually a full solution:
SURPRISE! It doesn't necessarily work.
But I'm not doing that in my proof, I'm using my construction on your proposed full solution (H(G), as far as I can tell), not P.
not active here but active on discord
κ is weakly mahlo iff the set of regulars less than κ is stationary in κ.
κ is weakly mahlo iff the set of regulars less than κ is stationary in κ.
Re: Is Colorized life more powerful than life computationally?
They're equivalent models, which is the whole point: if you had a coloured life pattern that solves the halting problem for Turing machines, then you'd be able to emulate that coloured life pattern with a Turing machine, and therefore you'd have a Turing machine that solves the halting problem.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
your proof is the standard proof of undecidability of halting problem using invert of the diagonal, and I'm saying the diagonalization argument does not work for me. even Turing himself had the same feeling and find it necessary to give a second proof for unsolvability of his satisfactoriness problem, although his second proof also use diagonalization but not invert of the diagonal.
forget about life for a moment and consider turing machine and colored turing machine
saying you can simulate a colored turing machine by a turing machine is like saying you can simulate colored life by life
Re: Is Colorized life more powerful than life computationally?
forget about life for a moment and consider turing machine and colored turing machinecalcyman wrote: ↑June 2nd, 2023, 1:44 pmThey're equivalent models, which is the whole point: if you had a coloured life pattern that solves the halting problem for Turing machines, then you'd be able to emulate that coloured life pattern with a Turing machine, and therefore you'd have a Turing machine that solves the halting problem.
is colored turing machine equivalent to turing machine ?
you can interpret the output of a colored turing machine differently so colored turing machine can express more algorithms than turing machine
by the way I didn't find any proof against the existence of a circle-free turing machine that solves the halting problem
all proof rely on the fact the halting decider accept an input
Re: Is Colorized life more powerful than life computationally?
Yes! You can just think of a "coloured Turing machine" as being a regular Turing machine with a larger set of states/symbols.
Note that the coloured Turing machine might not be equivalent to the original Turing machine without the colours, but it will be equivalent to some larger Turing machine; perhaps this is the source of confusion?
That's a non-sequitur: if you take a universal Turing machine, for example, then it can already run any algorithm, and adding colours (or anything else that's computable) cannot make it more powerful. If you gave it an uncomputable attachment such as a halting oracle, then yes it becomes more powerful computationally, but colourised life is computable so this doesn't apply here.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
if you color a universal turing machine then it's output will be colored and since it is universal you can express more algorithms with it. consider FRACTRAN POLYGAME as a universal machine that maps numbers from c2^2^n to 2^2^m , now if you color POLYGAME by randomly making it's fractions negative then it maps number frm c2^2^n to 2^2^m or -2^2^m , in this way I can give you more recipe to calculate a function, consider a POLYGAME number c such that it always maps n to 0 or -0 then there is no obvious way to diagonalize such a program.calcyman wrote: ↑June 3rd, 2023, 8:52 amThat's a non-sequitur: if you take a universal Turing machine, for example, then it can already run any algorithm, and adding colours (or anything else that's computable) cannot make it more powerful. If you gave it an uncomputable attachment such as a halting oracle, then yes it becomes more powerful computationally, but colourised life is computable so this doesn't apply here.
Re: Is Colorized life more powerful than life computationally?
let me give you an analogy, consider a mystery apple generator machine that has a setting m that can be set to any natural number
the mystery apple generator machine accept some green apple as input and sometimes output some green or red apple
now is there a setting m such that when you put n green apple inside, it always
output 1 green apple if n is equal to a setting number that outputs apple or
output 1 red apple if n is equal to a setting number that does not output any apple ?
by this analogy I meant that it is conceivable that the halting problem is solvable, people are just confused over a self referential presentation of the problem
Re: Is Colorized life more powerful than life computationally?
Yes, that's entirely consistent.raoofha wrote: ↑June 3rd, 2023, 9:57 amlet me give you an analogy, consider a mystery apple generator machine that has a setting m that can be set to any natural number
the mystery apple generator machine accept some green apple as input and sometimes output some green or red apple
now is there a setting m such that when you put n green apple inside, it always
output 1 green apple if n is equal to a setting number that outputs apple or
output 1 red apple if n is equal to a setting number that does not output any apple ?
I agree with you that you can't directly apply a diagonal argument to show that a 'coloured Turing machine' cannot solve the halting problem of ordinary Turing machines. But you can prove the nonexistence of such a machine by contradiction, ultimately relying on the result for ordinary Turing machines:
Specifically, if you have a 'coloured Turing machine' whose state transition function is computable, then it can be emulated by a Turing machine. So, supposing that there is a coloured Turing machine that solves the halting problem of ordinary Turing machines, you could emulate that with an ordinary Turing machine, and this too would be able to solve the halting problem of ordinary Turing machines. That contradicts the diagonal argument applied to ordinary Turing machines, so we can deduce that the original assumption (the existence of a coloured Turing machine with computable transition function that can solve the halting problem) is false.
Note that we've made the assumption that the 'coloured Turing machine' has a computable state transition function. If it didn't (for example, because it has access to an oracle for Turing machines), then this proof wouldn't go through, because of course it can't: an oracle machine can trivially solve the halting problem. But the original subject of discussion (colourised Life) does have a computable state transition function.
What do you do with ill crystallographers? Take them to the mono-clinic!