Is Colorized life more powerful than life computationally?

[calcyman]

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.

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.

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.

[raoofha]

it's been proven impossible.

it's all just a self referential confusion

[Entity Valkyrie 2]

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?

[wirehead]

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.

[raoofha]

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]

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.

[raoofha]

...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]

Can you reiterate what you find wrong about this argument:

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

[raoofha]

Can you reiterate what you find wrong about this argument:

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]

Can you reiterate what you find wrong about this argument:

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?

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".

[raoofha]

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

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]

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.

[raoofha]

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]

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.

[raoofha]

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]

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

[galoomba]

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]

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]

There is no Turing machine that can solve the halting problem. This is proven.

you have not read my previous comments

[galoomba]

There is no Turing machine that can solve the halting problem. This is proven.

you have not read my previous comments

I have. As I understand, you're trying to solve the halting problem with a Turing machine. That is proven to be impossible.

[azulavoir]

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]

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]

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]

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.

[raoofha]

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