Is Colorized life more powerful than life computationally?

[raoofha]

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 ?

[galoomba]

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 ?

no

[b3s23love]

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 ?

no

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.

[confocaloid]

...
no

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. (...)

[raoofha]

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.

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 answers

[b3s23love]

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.

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 answers

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]

you could do the same in regular Life by using two glider lanes for outputs. You don't need different-color gliders.

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

[b3s23love]

What do you mean by diagonalization?

[hotdogPi]

It can't output a red glider if it doesn't halt, as outputting that glider would be halting.

[raoofha]

What do you mean by diagonalization?

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.

[raoofha]

It can't output a red glider if it doesn't halt, as outputting that glider would be halting.

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"

[calcyman]

What do you mean by diagonalization?

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.

You can emulate coloured life with a Turing machine though, so it reduces to the proof of undecidability for Turing machines.

[raoofha]

You can emulate coloured life with a Turing machine though, so it reduces to the proof of undecidability for Turing machines.

no it does not reduce to the proof of undecidability for turing machine because you can emulate turing machine in colored life . why should one prefer turing machine over colored life ?

[pzq_alex]

You can emulate coloured life with a Turing machine though, so it reduces to the proof of undecidability for Turing machines.

no it does not reduce to the proof of undecidability for turing machine because you can emulate turing machine in colored life . why should one prefer turing machine over colored life ?

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.

[raoofha]

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.

I don't know how you can do that can you give me a reference to look for?
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

[Moosey]

because life patterns have the same behavior regardless of colors no counter example can be constructed

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.

[raoofha]

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.

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

[Moosey]

you didn't read my last comment. you're proof does not work

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:

as far as H is concerned P does not need to halt on any of it's input

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.

[calcyman]

You can emulate coloured life with a Turing machine though, so it reduces to the proof of undecidability for Turing machines.

no it does not reduce to the proof of undecidability for turing machine because you can emulate turing machine in colored life . why should one prefer turing machine over colored life ?

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.

[raoofha]

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.

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

[raoofha]

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.

forget about life for a moment and consider turing machine and colored turing machine

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

[calcyman]

is colored turing machine equivalent to turing machine ?

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?

you can interpret the output of a colored turing machine differently so colored turing machine can express more algorithms than turing machine

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.

[raoofha]

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.

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.

[raoofha]

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?

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

[calcyman]

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 ?

Yes, that's entirely consistent.

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.