## Is Colorized life more powerful than life computationally?

For general discussion about Conway's Game of Life.
calcyman
Moderator
Posts: 2906
Joined: June 1st, 2009, 4:32 pm

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
June 11th, 2023, 2:57 pm
do you believe that there is no finite algorithm (like a colored turing machine) that solves the halting problem
Yes.
without any proof ?
No. Any finite algorithm can be performed on a Turing machine, so if no Turing machine can solve the halting problem, then nor can any finite algorithm.

For your example of coloured Turing machines, I gave an explicit way of doing so (by creating a Turing machine with a symbol for every colour-symbol combination in your coloured Turing machine). You then made the non-standard restriction that I'm not allowed to change the alphabet, but this is irrelevant because there's an easy algorithm to convert an arbitrary Turing machine into a 2-symbol Turing machine.
because as I argued diagonalization argument does not apply to the set of colored turing machine (considering my new definition)
My point is that there's absolutely no need to apply a diagonal argument to the set of coloured Turing machines! The unsolvability of the halting problem by any finite algorithm is the logical conclusion of:

1. Turing machines cannot solve the halting problem
2. Anything that can be computed by a finite algorithm can be computed by a Turing machine

There's no diagonal argument involved in proving 2, which is the part that you're seeming to dispute.
raoofha wrote:
June 11th, 2023, 3:33 pm
I'm trying to come up with a formal system that is complete and sound and get around the Godel's incompleteness theorems
There are plenty of such formal systems: the first-order theory of algebraically closed fields of characteristic zero has this property. The caveat is that such systems are necessarily weak in their expressive power; you can't formalise the halting problem in such a system.
raoofha wrote:
June 11th, 2023, 3:33 pm
my approach is similar to James Anderson Transmathematics, he is trying to totalize mathematics, I'm trying to totalizing computation
Yes, and both approaches are futile. There was a time pre-Godel where mathematicians such as Hilbert pursued this goal -- see https://en.wikipedia.org/wiki/Hilbert%27s_program -- but this is no longer taken seriously because it's been proven impossible.
What do you do with ill crystallographers? Take them to the mono-clinic!

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

calcyman wrote:
June 11th, 2023, 5:37 pm
it's been proven impossible.
it's all just a self referential confusion

Entity Valkyrie 2
Posts: 1716
Joined: February 26th, 2019, 7:13 pm
Contact:

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
June 12th, 2023, 8:25 am
calcyman wrote:
June 11th, 2023, 5:37 pm
it's been proven impossible.
it's all just a self referential confusion
The halting problem is solvable if one adds restrictions like “a program cannot refer to itself”, which prohibits programs like
g() = if h(g) then g(). But that would no longer be Turing-complete.

Also, how would the halting problem work if the machine, apart from “Halt” and “Doesn't halt”, can somehow “Half-halt”? How does fuzzy logic work with this?
Bx222 IS MY WORST ENEMY.

My recent rules:
StateInvestigator 3.0
B3-kq4ej5i6ckn7e/S2-i34q6a7
B3-kq4ej5y6c/S2-i34q5e
Move the Box

Posts: 225
Joined: June 18th, 2022, 2:37 pm
Location: Under a thinking cap
Contact:

### Re: Is Colorized life more powerful than life computationally?

I had a bit of fun trying to write a program last year that given a Thue program, would try to get a probability of the program halting. Thue programs can be written as NFAs, so the algorithm tried to look for self-referential rules and loops of states, but it never worked to certainty. You can always guess the chance of a program halting, but you can't ever give a definitive answer.
Langton's ant: Can't play the drums, can be taught.

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

Entity Valkyrie 2 wrote:
September 26th, 2023, 12:10 pm
Also, how would the halting problem work if the machine, apart from “Halt” and “Doesn't halt”, can somehow “Half-halt”? How does fuzzy logic work with this?
imagine we have a partial solution to the halting problem meaning we have program P(p) that on most input halt with output 0 or 1 or does not halt on some input
now consider the following program

Code: Select all

function H(p)
{
let q = Substn(H,p);
if(P(q))
{
let r = P(p);
console.log(r);
}
else
{
console.log(0);
while(1);
}
}
now I claim that H(p) solves the halting problem
H(p) is basically saying: "if I can prove that I halt then I can prove that whether p halt or not otherwise if I can prove that I don't halt then p does not halt"

olivia enessemir
Posts: 16
Joined: August 7th, 2023, 5:29 pm

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
June 12th, 2023, 8:25 am
calcyman wrote:
June 11th, 2023, 5:37 pm
it's been proven impossible.
it's all just a self referential confusion
...How?? The proof that the halting problem is, in general, unsolvable doesn't assume its own conclusion; the proof relies on a sort of self-reference yes, but this self-reference isn't in the logical structure of the proof, so there's not any problem with the logic.
omelette

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

olivia enessemir wrote:
September 27th, 2023, 12:08 pm
...How?? The proof that the halting problem is, in general, unsolvable doesn't assume its own conclusion; the proof relies on a sort of self-reference yes, but this self-reference isn't in the logical structure of the proof, so there's not any problem with the logic.
as far as I understand and studied the halting problem all proof of undecidability rely on self-reference that does NOT mean that there is something wrong with the logic but it imply at least for me maybe there is a yet to be discovered way to avoid self-negation. for example, maybe there is a turing machine U(m) that halts with the output of turing machine m, and return the tape WITHOUT halting if m does not halt

pzq_alex
Posts: 787
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

### Re: Is Colorized life more powerful than life computationally?

• Fix a version of colorized Life (say DoubleB3S23);
• Any colorized Life pattern can be emulated in Life;
• Thus, any function computed by colorized Life can be computed by Life;
• Thus colorized Life is at most as powerful as Life (in fact equally powerful).
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

pzq_alex wrote:
September 28th, 2023, 9:00 am
there is nothing wrong, you are right if you believe that you can not solve the halting problem with Life then you can also believe that you can not solve it by colored Life.
I put my idea for colored Life aside for a while now I just responding to previous comments about the halting problem

olivia enessemir
Posts: 16
Joined: August 7th, 2023, 5:29 pm

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
September 28th, 2023, 10:31 am
pzq_alex wrote:
September 28th, 2023, 9:00 am
there is nothing wrong, you are right if you believe that you can not solve the halting problem with Life then you can also believe that you can not solve it by colored Life.
I put my idea for colored Life aside for a while now I just responding to previous comments about the halting problem
... so you think it's possible that regular Life can solve the halting problem?
raoofha wrote:
September 27th, 2023, 2:35 pm
as far as I understand and studied the halting problem all proof of undecidability rely on self-reference that does NOT mean that there is something wrong with the logic but it imply at least for me maybe there is a yet to be discovered way to avoid self-negation.
Well, no, there isn't. It doesn't matter, because the proof of the halting problem's undecidability applies universally for any system that's equivalent to a turing machine, e.g. Life, Colorized Life, etcetera. It doesn't matter how clever you are, "for all" still means "for all", not "for all things that aren't cleverly constructed".
omelette

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

olivia enessemir wrote:
September 29th, 2023, 11:44 am
... so you think it's possible that regular Life can solve the halting problem?
if you consider the kind of solution that I have in mind then yes it is conceivable
olivia enessemir wrote:
September 29th, 2023, 11:44 am
Well, no, there isn't. It doesn't matter, because the proof of the halting problem's undecidability applies universally for any system that's equivalent to a turing machine, e.g. Life, Colorized Life, etcetera. It doesn't matter how clever you are, "for all" still means "for all", not "for all things that aren't cleverly constructed".
there are hypercomputational or super-Turing models of computation that can solve the halting problem, the problem is physical realizability of those models, and some people questioned the validity of Halting Theorem by paraconsistent models of computation but my idea is something in between I have an intuition that everything is kind-of-decidable by classical models of computation meaning a turing machine U(m) that halts if m halts or return the tape WITHOUT halting if m does not halt

olivia enessemir
Posts: 16
Joined: August 7th, 2023, 5:29 pm

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
September 29th, 2023, 1:24 pm
there are hypercomputational or super-Turing models of computation that can solve the halting problem
Yes, things like turing oracles can solve the halting problem, but it's very obvious that CGoL is equivalent only to turing machines and so cannot.
omelette

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

olivia enessemir wrote:
October 1st, 2023, 2:13 pm
Yes, things like turing oracles can solve the halting problem, but it's very obvious that CGoL is equivalent only to turing machines and so cannot.
if there is a turing machine U as I described before then Life can solve the halting problem by simulating U

olivia enessemir
Posts: 16
Joined: August 7th, 2023, 5:29 pm

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
October 2nd, 2023, 3:36 am
if there is a turing machine U as I described before then Life can solve the halting problem by simulating U
How do you expect to go from "U halts iff the input turing machine halts" to "you can tell within finite time based on the current state of U whether the input turing machine halts"?
Also, obviously, no, life cannot solve the halting problem.
omelette

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

olivia enessemir wrote:
October 2nd, 2023, 10:54 am
How do you expect to go from "U halts iff the input turing machine halts" to "you can tell within finite time based on the current state of U whether the input turing machine halts"?
Also, obviously, no, life cannot solve the halting problem.
I didn't quite get what you mean, assuming that there is a turing machine U then you run U on the given input and wait until U halts or return the tape after that you know that the given input halts or does not halt

azulavoir
Posts: 56
Joined: September 20th, 2023, 10:28 am

### Re: Is Colorized life more powerful than life computationally?

And how long does "Wait until U halts" take? How do you know when to stop waiting?

galoomba
Posts: 109
Joined: February 28th, 2023, 10:19 am

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
October 2nd, 2023, 3:36 am
if there is a turing machine U as I described before then Life can solve the halting problem by simulating U
There is no Turing machine that can solve the halting problem. This is proven.

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

azulavoir wrote:
October 2nd, 2023, 4:53 pm
And how long does "Wait until U halts" take? How do you know when to stop waiting?
when U goes into a halting state then you know

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

galoomba wrote:
October 2nd, 2023, 7:24 pm
There is no Turing machine that can solve the halting problem. This is proven.

galoomba
Posts: 109
Joined: February 28th, 2023, 10:19 am

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
October 3rd, 2023, 2:18 am
galoomba wrote:
October 2nd, 2023, 7:24 pm
There is no Turing machine that can solve the halting problem. This is proven.
I have. As I understand, you're trying to solve the halting problem with a Turing machine. That is proven to be impossible.

azulavoir
Posts: 56
Joined: September 20th, 2023, 10:28 am

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
October 3rd, 2023, 2:17 am
azulavoir wrote:
October 2nd, 2023, 4:53 pm
And how long does "Wait until U halts" take? How do you know when to stop waiting?
when U goes into a halting state then you know
Define a single time in the future, after N iterations of U, where you can be certain that U has halted, then. Otherwise you can't say you know.

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

galoomba wrote:
October 3rd, 2023, 10:39 am
I have. As I understand, you're trying to solve the halting problem with a Turing machine. That is proven to be impossible.
that depend on your definition of "solve", it is proven using the classical logic that the halting problem is semi-decidable and my definition of the turing machine U is perfectly compatible with semi-decidability of the halting problem
if you want to believe that the halting problem can not be solved then you must prove that there is no turing machine U

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

azulavoir wrote:
October 3rd, 2023, 11:49 am
Define a single time in the future, after N iterations of U, where you can be certain that U has halted, then. Otherwise you can't say you know.
are you saying there is no turing machine U as I specified ? assuming there is and I find it then I can tell you how it works

olivia enessemir
Posts: 16
Joined: August 7th, 2023, 5:29 pm

### Re: Is Colorized life more powerful than life computationally?

raoofha wrote:
October 3rd, 2023, 12:31 pm
that depend on your definition of "solve" ... semi-decidable ...
So you're just defining "solving the halting problem" as "being able to return "X halts" whenever X halts [but not necessarily ever returning "X doesn't halt" when it doesn't]"? Well then of course the halting problem is "solvable", but this is a really weak and kind of bizarre notion of "solvability", and I'm not sure why you'd assume that anyone would be able to tell that's what you meant.
omelette

raoofha
Posts: 41
Joined: June 2nd, 2023, 2:06 am

### Re: Is Colorized life more powerful than life computationally?

olivia enessemir wrote:
October 3rd, 2023, 12:41 pm
So you're just defining "solving the halting problem" as "being able to return "X halts" whenever X halts [but not necessarily ever returning "X doesn't halt" when it doesn't]"? Well then of course the halting problem is "solvable", but this is a really weak and kind of bizarre notion of "solvability", and I'm not sure why you'd assume that anyone would be able to tell that's what you meant.
as I wrote before the turing machine U halts if the given input halts and return the tape WITHOUT halting if the given input does not halt, so for all input you know that a given input halt or does not halt that's sound to me like a solution assuming I can find U