ConwayLife.com

hotdogPi wrote: October 4th, 2023, 2:32 pm Can we halt this thread?

yes

... then U doesn't really solve the halting problem. Solving the halting problem for only some cases is possible but kind of pointless.

as I wrote many times U(m) halts on m if m halts and return the tape WITHOUT halting if m does not halt
for me it is an interesting challenge to find U
if you ...

and you actually know that a given non-halting input doesn't halt after a finite amount of time, then if that can be done with a regular turing machine, you can construct a contradiction using the same construction that has already been mentioned many, many, many times in this thread.

how do you ...

when does it return the tape?
how does it know when to return the tape? How does it know the input does or doesn't halt so it can determine whether to return the tape/etcetera??

those are things that have to be discovered, but U can not solve the halting problem by having a "return the tape ...

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

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

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

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

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

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

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

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

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

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

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

calcyman wrote: June 11th, 2023, 5:37 pm it's been proven impossible.

it's all just a self referential confusion

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

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

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

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

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

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

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

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

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