Is Colorized life more powerful than life computationally?

[b3s23love]

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.

The way I thought of saying this is that there is no "super-Turing-complete" system that's more powerful than other Turing-complete systems. A Turing-complete system can already compute anything that's computable, so Colored Life isn't more powerful than Life.

[raoofha]

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.

each turing machine is a valid colored turing machine just like that each life is a valid colored life
the set of turing machines is a subset of colored turing machines and I'm claiming that there is a colored turing machine that solves the halting problem
so you can not use the diagonal argument for a subset of valid algorithms and claim there is a contradiction

[calcyman]

I'm claiming that there is a colored turing machine that solves the halting problem

Right! But my point is that, if you give me a description of your coloured Turing machine that solves the halting problem, then I can construct a non-coloured Turing machine that also solves the halting problem.

My non-coloured Turing machine would simulate your coloured Turing machine until it halts, check the colour (red or blue) that your machine produces as output, write down a symbol on the tape to represent that colour, and then halt.

But, by the diagonal argument applied only to non-coloured Turing machines, my non-coloured Turing machine can't exist. Contradiction.

[raoofha]

Right! But my point is that, if you give me a description of your coloured Turing machine that solves the halting problem, then I can construct a non-coloured Turing machine that also solves the halting problem.

My non-coloured Turing machine would simulate your coloured Turing machine until it halts, check the colour (red or blue) that your machine produces as output, write down a symbol on the tape to represent that colour, and then halt.

But, by the diagonal argument applied only to non-coloured Turing machines, my non-coloured Turing machine can't exist. Contradiction.

no you can not do that, your non-colored turing machine is not a valid turing machine. you can not detect a color of a symbol a valid turing machine can only switch a color of a symbol or override it's color or leave it on changed or mapped it another symbol but if you try to detect a color of a symbol that is not permitted if you do that then the universal colored turing machine does not do what you expect it to do
for example if you construct a counter example G for the assumed solution to the halting problem H
then UCTM(H,G)=1 in red because G is not a valid turing machine and UCTM(G,0) does not halt when you expect that G halts

[calcyman]

Right! But my point is that, if you give me a description of your coloured Turing machine that solves the halting problem, then I can construct a non-coloured Turing machine that also solves the halting problem.

My non-coloured Turing machine would simulate your coloured Turing machine until it halts, check the colour (red or blue) that your machine produces as output, write down a symbol on the tape to represent that colour, and then halt.

But, by the diagonal argument applied only to non-coloured Turing machines, my non-coloured Turing machine can't exist. Contradiction.

no you can not do that, your non-colored turing machine is not a valid turing machine

It absolutely is a valid Turing machine. To clarify: I'm taking your n-state m-symbol k-colour coloured Turing machine and building an n-state (km)-symbol non-coloured Turing machine by creating a symbol for each of the km (symbol, colour) ordered pairs.

but if you try to detect a color of a symbol that is not permitted

Yes, my machine doesn't have any colours; it's just reading a symbol. For example, if your coloured Turing machine has 4 symbols {0, 1, 2, 3} and 2 colours {red, blue}, then my non-coloured Turing machine has 8 symbols {R0, R1, R2, R3, B0, B1, B2, B3}.

[raoofha]

It absolutely is a valid Turing machine. To clarify: I'm taking your n-state m-symbol k-colour coloured Turing machine and building an n-state (km)-symbol non-coloured Turing machine by creating a symbol for each of the km (symbol, colour) ordered pairs.

Yes, my machine doesn't have any colours; it's just reading a symbol. For example, if your coloured Turing machine has 4 symbols {0, 1, 2, 3} and 2 colours {red, blue}, then my non-coloured Turing machine has 8 symbols {R0, R1, R2, R3, B0, B1, B2, B3}.

a universal turing machine must have a fixed alphabet for it's input and output you are using an input alphabet that is not part of the universal [colored] turing machine's input alphabet

[calcyman]

It absolutely is a valid Turing machine. To clarify: I'm taking your n-state m-symbol k-colour coloured Turing machine and building an n-state (km)-symbol non-coloured Turing machine by creating a symbol for each of the km (symbol, colour) ordered pairs.

Yes, my machine doesn't have any colours; it's just reading a symbol. For example, if your coloured Turing machine has 4 symbols {0, 1, 2, 3} and 2 colours {red, blue}, then my non-coloured Turing machine has 8 symbols {R0, R1, R2, R3, B0, B1, B2, B3}.

a universal turing machine must have a fixed alphabet for it's input and output you are using an input alphabet that is not part of the universal [colored] turing machine's input alphabet

It's still a Turing machine, so the original diagonal argument still applies. Even if you do insist on restricting the alphabet, then you can convert any Turing machine into an equivalent 2-symbol Turing machine by increasing the number of states.

[raoofha]

It's still a Turing machine, so the original diagonal argument still applies. Even if you do insist on restricting the alphabet, then you can convert any Turing machine into an equivalent 2-symbol Turing machine by increasing the number of states.

and you can color any 2-symbol Turing machine to express more algorithms, and the diagonal argument does not apply to the set of 2-symbol colored turing machine

[raoofha]

It's still a Turing machine, so the original diagonal argument still applies. Even if you do insist on restricting the alphabet, then you can convert any Turing machine into an equivalent 2-symbol Turing machine by increasing the number of states.

let me give you another analogy, if you translate an invalid English sentence to Chinese you might get a valid Chinese sentence but that does not mean that your original English sentence is valid
similarly if you translate a supposed counterexample for assumed solution of the halting problem to a colorless turing machine with higher number of symbols that does not mean that your original counterexample is a valid colored turing machine

[pzq_alex]

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

If a colored Life pattern can solve the halting problem, you can emulate it with a Turing machine and then proceed using the standard diagonalization argument.

[raoofha]

If a colored Life pattern can solve the halting problem, you can emulate it with a Turing machine and then proceed using the standard diagonalization argument.

I explained in my previous comments that does not work
the set of turing machines is a subset of colored turing machines like the set of life patterns are a subset of colored life patterns
you have to apply the diagonal argument to the set of colored turing machines and you can't do that

[Moosey]

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

you can emulate accepting input by imagining that the turing machine has extra states necessary to write the input onto the tape before returning to the origin to actually do computation

saying you can simulate a colored turing machine by a turing machine is like saying you can simulate colored life by life

... which you can. It's just that you need metacells.

the set of turing machines is a subset of colored turing machines

that doesn't make the latter any more powerful than the former a priori.

Though the set of turing machines is a subset of the set of colored turing machines, every colored turing machine may be emulated by a colorless one. Therefore it turns out that colored turing machines are no more powerful than colorless ones.

[raoofha]

you can emulate accepting input by imagining that the turing machine has extra states necessary to write the input onto the tape before returning to the origin to actually do computation

that doesn't prove anything, you have to give a counter example for an inputless solution to the halting problem, notice that an inputless solution to the halting problem keeps outputing the digit of the halting sequence h_0,h_1,...,h_n,... where h_i is equal to 1 if ith turing machine halts and 0 if ith turing machine does not halt

... which you can. It's just that you need metacells.

again using metacells doesn't prove anything, it just show there is a larger pattern that wiggle around, you have to compare the two models side by side not inside of each other

that doesn't make the latter any more powerful than the former a priori.

Though the set of turing machines is a subset of the set of colored turing machines, every colored turing machine may be emulated by a colorless one. Therefore it turns out that colored turing machines are no more powerful than colorless ones.

again you have to compare the two models side by side not inside of each other
saying every colored turing machine can be emulated by colorless one is like saying that every English sentence can be written in Basic English so English is no more powerful than Basic English
a perfect language must distinguish an invalid sentence from a valid sentence and similarly a perfect model of computation must distinguish an invalid algorithm from a valid algorithm
the set of turing machines contains invalid algorithms but I conjecture that the set of colored turing machine does not contain invalid algorithms
so I conjecture that colored turing machine is a perfect model of computation

[Moosey]

saying every colored turing machine can be emulated by colorless one is like saying that every English sentence can be written in Basic English so English is no more powerful than Basic English

I'm done
I give up
I literally have no idea how on earth you could possibly use this kind of argument as anything but a justification for the fact that colored Turing machines are no more powerful than Turing machines
As such, I have no counterargument

[raoofha]

I'm done
I give up
I literally have no idea how on earth you could possibly use this kind of argument as anything but a justification for the fact that colored Turing machines are no more powerful than Turing machines
As such, I have no counterargument

I can give another argument

suppose there is a 2-symbol 2-color turing machines H that solves the halting problem for 2-symobl 2-color turing machines by output
1 in green if the input is a 2-symbol 2-color turing machine that halts on blank input and
1 in red if the input is a 2-symbol 2-color turing machine that does not halt on blank input and
0 if the input is not a valid 2-symbol 2-color turing machine

now you are saying that you can simulate all 2-symbol 2-color turing machines (we assume that blank symbol has no color) with a 2-symbol turing machine called UC

how can UC simulate H ? it has to output different symbols for green 1 and red 1 and 0 for example 11 and 1 and 0
now we can construct a 2-symbol turing machine Q using UC and H such that it halts if UC(H,Q)=1 and it does not halt if UC(H,Q)=11
so H can not be a solution to the halting problem

that is my understanding of your counter argument, am I right?

but that doesn't prove anything because UC(H,Q) can be 0

[Moosey]

but that doesn't prove anything because UC(H,Q) can be 0

Wel, no, it can't be, because it's going to be a valid Turing machine, and by your definition that means it's not going to output 0, which only happens if it's not a valid turing machine.


Out of curiosity, exactly where do you think is the flaw in the following reasoning?
1. Turing machines can emulate colorized turing machines
2. therefore if something is computable by a colorized turing machine it would be computable by a turing machine
3. therefore if colorized turing machines could solve the halting problem for turing machines then so could turing machines
4. normal turing machines cannot solve the halting problem, so colorized turing machines cannot solve the halting problem.

[raoofha]

Wel, no, it can't be, because it's going to be a valid Turing machine, and by your definition that means it's not going to output 0, which only happens if it's not a valid turing machine.

Out of curiosity, exactly where do you think is the flaw in the following reasoning?
1. Turing machines can emulate colorized turing machines
2. therefore if something is computable by a colorized turing machine it would be computable by a turing machine
3. therefore if colorized turing machines could solve the halting problem for turing machines then so could turing machines
4. normal turing machines cannot solve the halting problem, so colorized turing machines cannot solve the halting problem.

technically there is no flaw relative to your logic if you use a non-classical logic then the undecidability of Halting problem does not follow

[raoofha]

Wel, no, it can't be, because it's going to be a valid Turing machine, and by your definition that means it's not going to output 0, which only happens if it's not a valid turing machine.

there is another way to look at it, I can remove all turing machines from the set of colored turing machines
in this way Q is clearly not a valid colored turing machine

[dvgrn]

Wel, no, it can't be, because it's going to be a valid Turing machine, and by your definition that means it's not going to output 0, which only happens if it's not a valid turing machine.

there is another way to look at it, I can remove all turing machines from the set of colored turing machines
in this way Q is clearly not a valid colored turing machine

Your responses in this thread haven't been making a lot of sense to me for a while, but this message seems to create a whole new level of confusion.

Why would you "remove all turing machines from the set of colored turing machines"? Colored Turing machines are still Turing machines, so it seems like you've either created a convoluted definition of the empty set, or you're not wording things clearly enough for me to understand.

In any case, maybe it's time to say one more time that colorized Life can not possibly be more "computationally powerful" than regular Life, because regular Life is already Turing-complete. Everyone's responses to your posts have been very clear on this point.

Theoretically colorized Life might be more efficient at displaying some result. But questions of efficiency are spectacularly irrelevant for Turing-machine models in any case, and that's even more true for Turing machines modeled as Life patterns.

[raoofha]

Why would you "remove all turing machines from the set of colored turing machines"? Colored Turing machines are still Turing machines, so it seems like you've either created a convoluted definition of the empty set, or you're not wording things clearly enough for me to understand.

colored turing machines are not turing machines, turing machines are a subset of colored turing machines
if you ignore colors of symbols of a colored turing machine you must get a turing machine with the same behavior
so you can remove all turing machines from the set of colored turing machines without losing turing completeness

if colored turing machine instructions are of the form (state,read-symbol,next-state,write-symbol,direction)
then for a 2-symbol 2-color turing machine (where blank symbol is 0 and it has no color and + and - are two non-blank symbol representing two colors)
if you have an instruction like this
(q_i, +, q_j, 0, d)
then you must also have this instruction
(q_i, -, q_j, 0, d)
and you can not have the following two instruction together
(q_i, +, q_j, 0, d)
(q_i, -, q_j, +/-, d)

I can try to explain my idea more clearly, maybe create a web app for colored turing machines

In any case, maybe it's time to say one more time that colorized Life can not possibly be more "computationally powerful" than regular Life, because regular Life is already Turing-complete. Everyone's responses to your posts have been very clear on this point.

Church-Turing Thesis is not set in stone

[calcyman]

In any case, maybe it's time to say one more time that colorized Life can not possibly be more "computationally powerful" than regular Life, because regular Life is already Turing-complete. Everyone's responses to your posts have been very clear on this point.

Church-Turing Thesis is not set in stone

For phenomena in our physical universe, yes: there's always the (unlikely, but not disproven) possibility that there's some random undetected particle somewhere that is capable of acting as a halting oracle.

But anything that's describable by some finite state machine attached to a discrete memory can be converted into a Turing machine (or a 2-counter machine, or an expression in SK combinatory logic, or a FRACTRAN program, or whatever) with equivalent behaviour

[dvgrn]

colored turing machines are not turing machines, turing machines are a subset of colored turing machines...

Okay, you apparently meant something like "remove the set of single-color Turing machines from the set of colored Turing machines". Whenever you say "Turing machine", you're meaning "single-color Turing machine" -- I think.

Put yourself in the place of someone who doesn't already know what you're thinking. If you leave out the "single-color" adjective, your statement is not likely to come across clearly, because technically it says something that's clearly self-contradictory.

Church-Turing Thesis is not set in stone

Maybe not, but it sure is plausible -- given that everybody's attempts to define computability turn out to all be exactly equivalent to each other.. Your approach here seems to be to argue without evidence that adding more colors to a Life-based computing device makes some kind of interesting difference to computability.

To say the least, this is a highly odd and awkward computing model to choose to look at. The unnecessary extra complexity may be helping to obscure the logical leap(s) that can't actually be justified.

[raoofha]

For phenomena in our physical universe, yes: there's always the (unlikely, but not disproven) possibility that there's some random undetected particle somewhere that is capable of acting as a halting oracle.

I don't know anything about particles I just understand logic
it is logically possible to solve the halting problem using logic alone no particle is needed and it is sad that people think and teach otherwise
even Roger Penrose wrote "... mathematical understanding might be the result of some algorithm that is unsound or unknowable, or possibly sound and knowable but not knowably sound ..." in his book "Shadows of the Mind"

But anything that's describable by some finite state machine attached to a discrete memory can be converted into a Turing machine (or a 2-counter machine, or an expression in SK combinatory logic, or a FRACTRAN program, or whatever) with equivalent behaviour

do you believe that there is no finite algorithm (like a colored turing machine) that solves the halting problem without any proof ?
because as I argued diagonalization argument does not apply to the set of colored turing machine (considering my new definition)

[raoofha]

Okay, you apparently meant something like "remove the set of single-color Turing machines from the set of colored Turing machines". Whenever you say "Turing machine", you're meaning "single-color Turing machine" -- I think.

yes

Put yourself in the place of someone who doesn't already know what you're thinking. If you leave out the "single-color" adjective, your statement is not likely to come across clearly, because technically it says something that's clearly self-contradictory.

clearly you don't have the same intuition as me

Maybe not, but it sure is plausible -- given that everybody's attempts to define computability turn out to all be exactly equivalent to each other.. Your approach here seems to be to argue without evidence that adding more colors to a Life-based computing device makes some kind of interesting difference to computability.

To say the least, this is a highly odd and awkward computing model to choose to look at. The unnecessary extra complexity may be helping to obscure the logical leap(s) that can't actually be justified.

it is not a highly odd and awkward computing model, it's clear that I haven't explained my idea well enough
I'm trying to come up with a formal system that is complete and sound and get around the Godel's incompleteness theorems
my approach is similar to James Anderson Transmathematics, he is trying to totalize mathematics, I'm trying to totalizing computation

life the universe and everything is connected to the diagonalization argument

[Hippo.69]

I am surprised how long you are talking about the topic.
Yes you can simulate one model using the other.
Of course there could be complexity issues (I have not tought about it), it would be interesting if there would be e.a. exponential speedup (for some classes of problems).
But definitely we are still in L_0 (Chomski).
And while the "algorithm" has final description, there is countable number of them and therefore uncountable number of languages are not recognized by them. ... howgh