ConwayLife.com

Posted: **June 11th, 2023, 5:37 pm**

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.

Posted: **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

Posted: **September 26th, 2023, 12:10 pm**

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?

Posted: **September 26th, 2023, 3:25 pm**

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.

Posted: **September 27th, 2023, 10:24 am**

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"

Posted: **September 27th, 2023, 12:08 pm**

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.

Posted: **September 27th, 2023, 2:35 pm**

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

Posted: **September 28th, 2023, 9:00 am**

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

Posted: **September 28th, 2023, 10:31 am**

pzq_alex wrote: September 28th, 2023, 9:00 am 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

Posted: **September 29th, 2023, 11:44 am**

raoofha wrote: September 28th, 2023, 10:31 am
pzq_alex wrote: September 28th, 2023, 9:00 am 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?

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

Posted: **September 29th, 2023, 1:24 pm**

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

Posted: **October 1st, 2023, 2:13 pm**

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.

Posted: **October 2nd, 2023, 3:36 am**

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

Posted: **October 2nd, 2023, 10:54 am**

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.

Posted: **October 2nd, 2023, 2:38 pm**

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

Posted: **October 2nd, 2023, 4:53 pm**

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

Posted: **October 2nd, 2023, 7:24 pm**

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.

Posted: **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

Posted: **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.

you have not read my previous comments

Posted: **October 3rd, 2023, 10:39 am**

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

Posted: **October 3rd, 2023, 11:49 am**

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.

Posted: **October 3rd, 2023, 12:31 pm**

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

Posted: **October 3rd, 2023, 12:38 pm**

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

Posted: **October 3rd, 2023, 12:41 pm**

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.

Posted: **October 3rd, 2023, 12:45 pm**

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

ConwayLife.com

Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?

Re: Is Colorized life more powerful than life computationally?