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.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.
Is Colorized life more powerful than life computationally?
Re: Is Colorized life more powerful than life computationally?
Last edited by b3s23love on June 3rd, 2023, 1:12 pm, edited 1 time in total.
Support Conway's Story Mode!
Re: Is Colorized life more powerful than life computationally?
each turing machine is a valid colored turing machine just like that each life is a valid colored lifecalcyman wrote: ↑June 3rd, 2023, 10:16 amsupposing 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.
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
Re: Is Colorized life more powerful than life computationally?
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.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
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 docalcyman wrote: ↑June 3rd, 2023, 12:24 pmRight! 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.
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
Re: Is Colorized life more powerful than life computationally?
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.raoofha wrote: ↑June 3rd, 2023, 1:34 pmno you can not do that, your non-colored turing machine is not a valid turing machinecalcyman wrote: ↑June 3rd, 2023, 12:24 pmRight! 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.
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}.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
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 alphabetcalcyman wrote: ↑June 3rd, 2023, 1:50 pmIt 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}.
Re: Is Colorized life more powerful than life computationally?
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 wrote: ↑June 3rd, 2023, 2:27 pma 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 alphabetcalcyman wrote: ↑June 3rd, 2023, 1:50 pmIt 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}.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
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
Re: Is Colorized life more powerful than life computationally?
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
Re: Is Colorized life more powerful than life computationally?
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 wrote: ↑June 2nd, 2023, 12:04 pmI 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
\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 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
Re: Is Colorized life more powerful than life computationally?
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
... which you can. It's just that you need metacells.
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.
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?
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
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
again you have to compare the two models side by side not inside of each otherMoosey wrote: ↑June 6th, 2023, 12:56 pmthat 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.
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
Re: Is Colorized life more powerful than life computationally?
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
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?
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
Re: Is Colorized life more powerful than life computationally?
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.
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?
technically there is no flaw relative to your logic if you use a non-classical logic then the undecidability of Halting problem does not followMoosey wrote: ↑June 9th, 2023, 10:11 pmWel, 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.
Re: Is Colorized life more powerful than life computationally?
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
Re: Is Colorized life more powerful than life computationally?
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.
Re: Is Colorized life more powerful than life computationally?
colored turing machines are not turing machines, turing machines are a subset of colored turing machinesdvgrn wrote: ↑June 11th, 2023, 10:43 amWhy 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.
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
Church-Turing Thesis is not set in stonedvgrn wrote: ↑June 11th, 2023, 10:43 amIn 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.
Re: Is Colorized life more powerful than life computationally?
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.raoofha wrote: ↑June 11th, 2023, 1:19 pmChurch-Turing Thesis is not set in stonedvgrn wrote: ↑June 11th, 2023, 10:43 amIn 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.
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
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Is Colorized life more powerful than life computationally?
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.
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.
Re: Is Colorized life more powerful than life computationally?
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"
do you believe that there is no finite algorithm (like a colored turing machine) that solves the halting problem without any proof ?calcyman wrote: ↑June 11th, 2023, 2:10 pmBut 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
because as I argued diagonalization argument does not apply to the set of colored turing machine (considering my new definition)
Re: Is Colorized life more powerful than life computationally?
yes
clearly you don't have the same intuition as me
it is not a highly odd and awkward computing model, it's clear that I haven't explained my idea well enoughdvgrn wrote: ↑June 11th, 2023, 2:41 pmMaybe 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.
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
Re: Is Colorized life more powerful than life computationally?
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
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