Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Did Turing prove the undecidability of the halting problem?

arxiv.org

Post reply on HN
Print view View original

101–110 of 116 posts

Re: Did Turing prove the undecidability of the halting problem?

#101

Post by FartyMcFarter »

Maxatar wrote: post #100
FartyMcFarter wrote: post #94

Earlier quoted context omitted.

> For any single program, one of these two functions will correctly output whether it halts or not. Saying "one of these functions is correct" is not a decision procedure. You actually need to decide which one of them is correct. > This is why it's not very meaningful to talk about the decidability of particular Turing Machines I disagree. There are particular Turing machines whose decidability is extremely meaningfu…

>Saying "one of these functions is correct" is not a decision procedure. You actually need to decide which one of them is correct. That's precisely what a decision procedure is, it's an algorithm that takes as input the description of a Turing machine, and an input, and returns true if and only if the Turing machine halts when given the input. You are using the term "decide" as if there were some kind of agency invol…

> You are using the term "decide" as if there were some kind of agency involved, like you have to actually "choose" what is correct or incorrect

Isn't this literally what a decision procedure is? It's an algorithm that always outputs the correct answer, not one which tells you "the correct answer is either true or false". I'm not talking about agency or consciousness.

Re: Did Turing prove the undecidability of the halting problem?

#102

Post by Maxatar »

FartyMcFarter wrote: post #101
Maxatar wrote: post #100

Earlier quoted context omitted.

>Saying "one of these functions is correct" is not a decision procedure. You actually need to decide which one of them is correct. That's precisely what a decision procedure is, it's an algorithm that takes as input the description of a Turing machine, and an input, and returns true if and only if the Turing machine halts when given the input. You are using the term "decide" as if there were some kind of agency invol…

> You are using the term "decide" as if there were some kind of agency involved, like you have to actually "choose" what is correct or incorrect Isn't this literally what a decision procedure is? It's an algorithm that always outputs the correct answer, not one which tells you "the correct answer is either true or false". I'm not talking about agency or consciousness.

One of the two algorithms I posted tells you the correct answer for any specific Turing machine, so for any given Turing machine one of them is a decision procedure for it.

Re: Did Turing prove the undecidability of the halting problem?

#103

Post by auggierose »

anon291 wrote: post #86
auggierose wrote: post #70

Earlier quoted context omitted.

I don't believe that either. But every set of rational numbers bounded from above has a least upper bound in the reals.

That's my point. I don't believe they do. I don't believe the reals are well defined since no one can name them. In general, I lean towards mathematical constructivism: https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_... I agree that computable real numbers exist, even if they're intractable to compute.

If only those things existed that have a name, the world would be a pretty small and boring place. Also, that would be a world entirely defined by humans, and that just doesn't make sense.

Re: Did Turing prove the undecidability of the halting problem?

#104

Post by FartyMcFarter »

Maxatar wrote: post #102
FartyMcFarter wrote: post #101

Earlier quoted context omitted.

> You are using the term "decide" as if there were some kind of agency involved, like you have to actually "choose" what is correct or incorrect Isn't this literally what a decision procedure is? It's an algorithm that always outputs the correct answer, not one which tells you "the correct answer is either true or false". I'm not talking about agency or consciousness.

One of the two algorithms I posted tells you the correct answer for any specific Turing machine, so for any given Turing machine one of them is a decision procedure for it.

Sure, that is trivially true, but I don't see how that statement is useful in any way.

Re: Did Turing prove the undecidability of the halting problem?

#105

Post by Maxatar »

FartyMcFarter wrote: post #104
Maxatar wrote: post #102

Earlier quoted context omitted.

One of the two algorithms I posted tells you the correct answer for any specific Turing machine, so for any given Turing machine one of them is a decision procedure for it.

Sure, that is trivially true, but I don't see how that statement is useful in any way.

Exactly, so then we agree, there is nothing useful about an algorithm that can decide whether one specific Turing machine halts. Utility only emerges from an algorithm that can decide whether entire classes of other Turing machines halt, not from whether a particular machine does.

Re: Did Turing prove the undecidability of the halting problem?

#106

Post by FartyMcFarter »

Maxatar wrote: post #105
FartyMcFarter wrote: post #104

Earlier quoted context omitted.

Sure, that is trivially true, but I don't see how that statement is useful in any way.

Exactly, so then we agree, there is nothing useful about an algorithm that can decide whether one specific Turing machine halts. Utility only emerges from an algorithm that can decide whether entire classes of other Turing machines halt, not from whether a particular machine does.

> there is nothing useful about an algorithm that can decide whether one specific Turing machine halts.

Yes there is. If someone gives me a working algorithm (this means one algorithm, not two algorithms either of which may work or not as you've been doing) which can provably decide whether the machine encoding the Goldbach conjecture halts or not, that is a very useful algorithm.

I must insist that giving two algorithms and saying "one of them works" without telling me which one works is is not a valid answer, since that is strictly different from giving a working algorithm which I can run in finite time in order to find out one correct answer.

You said this yourself earlier:

> The Turing machine that encodes the Goldbach conjecture proves the conjecture if it halts, and disproves the conjecture if it doesn't halt. That is an interesting and meaningful property of such a Turing machine.

Re: Did Turing prove the undecidability of the halting problem?

#107

Post by Maxatar »

FartyMcFarter wrote: post #106
Maxatar wrote: post #105

Earlier quoted context omitted.

Exactly, so then we agree, there is nothing useful about an algorithm that can decide whether one specific Turing machine halts. Utility only emerges from an algorithm that can decide whether entire classes of other Turing machines halt, not from whether a particular machine does.

> there is nothing useful about an algorithm that can decide whether one specific Turing machine halts. Yes there is. If someone gives me a working algorithm (this means one algorithm, not two algorithms either of which may work or not as you've been doing) which can provably decide whether the machine encoding the Goldbach conjecture halts or not, that is a very useful algorithm. I must insist that giving two algori…

I just think you're making a very subtle mistake here by mixing up the question of whether Fermat's Last Theorem (or Goldbach's Conjecture) is true with whether there is an algorithm that tells you that that specific theorem is true.

In my opinion, it's useful to know whether Fermat's Last Theorem is true, and that requires a proof. An algorithm that can only tell you whether a particular theorem is true is entirely useless.

For example, Sir Andrew Wiles proved that Fermat's Last Theorem is true, so would you reject an algorithm that simply returned true for any input as somehow being wrong? Would you only be happy if the algorithm wasted some energy doing some "computation", messing around with some variables and producing copious amounts of heat before telling you that Fermat's Last Theorem were true? Of course not. It doesn't matter what the algorithm does as an implementation detail, what matters is that the output is correct, not the heat it generates in the process.

Knowing a theorem is true is valuable. Having an algorithm that simply returns the correct answer about whether a particular theorem is true is entirely useless.

In general, an algorithm is only useful when it can be used for some arbitrarily large set of inputs. An algorithm that only works for one single instance is hardly an algorithm at all, it's nothing more than a lookup table. To be something more than a lookup table, it needs to work for an entire class of inputs, it needs to take an infinite number of possibilities and compress them down into the finite description of a process.

We know that no such algorithm can decide the halting problem for every single Turing Machine, but we can construct algorithms that can decide the halting problem for subsets of Turing machines, infinitely large subsets in fact.

Having an algorithm that just works for one single Turing machine... pretty meaningless.

Re: Did Turing prove the undecidability of the halting problem?

#108

Post by FartyMcFarter »

Maxatar wrote: post #107
FartyMcFarter wrote: post #106

Earlier quoted context omitted.

> there is nothing useful about an algorithm that can decide whether one specific Turing machine halts. Yes there is. If someone gives me a working algorithm (this means one algorithm, not two algorithms either of which may work or not as you've been doing) which can provably decide whether the machine encoding the Goldbach conjecture halts or not, that is a very useful algorithm. I must insist that giving two algori…

I just think you're making a very subtle mistake here by mixing up the question of whether Fermat's Last Theorem (or Goldbach's Conjecture) is true with whether there is an algorithm that tells you that that specific theorem is true. In my opinion, it's useful to know whether Fermat's Last Theorem is true, and that requires a proof. An algorithm that can only tell you whether a particular theorem is true is entirely…

A proper algorithm comes with a proof that it's correct. But even if I don't understand the proof, knowing the answer itself is useful.

Re: Did Turing prove the undecidability of the halting problem?

#109

Post by anon291 »

auggierose wrote: post #103
anon291 wrote: post #86

Earlier quoted context omitted.

That's my point. I don't believe they do. I don't believe the reals are well defined since no one can name them. In general, I lean towards mathematical constructivism: https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_... I agree that computable real numbers exist, even if they're intractable to compute.

If only those things existed that have a name, the world would be a pretty small and boring place. Also, that would be a world entirely defined by humans, and that just doesn't make sense.

Sorry, to be clear, it's irrelevant whether humans are doing it or someone else. They're not identifiable, and there's no example of such a thing. There are noncomputable reals which we can identify. I'm willing to say those exist. There are non-computable reals that we cannot identify (basic countability argument), that must exist as part of the reals if defined as they are.

But we've no example of them. They're just kind of there. They don't exist.

Either way, you don't need to argue with me. Much smarter thinkers than me have written extensively on it, and it's a widely held view. It's an indictment of one's own curiosity when the response to a new idea is to suggest the introducer is somehow lacking.

Re: Did Turing prove the undecidability of the halting problem?

#110

Post by auggierose »

anon291 wrote: post #109
auggierose wrote: post #103

Earlier quoted context omitted.

If only those things existed that have a name, the world would be a pretty small and boring place. Also, that would be a world entirely defined by humans, and that just doesn't make sense.

Sorry, to be clear, it's irrelevant whether humans are doing it or someone else. They're not identifiable, and there's no example of such a thing. There are noncomputable reals which we can identify. I'm willing to say those exist. There are non-computable reals that we cannot identify (basic countability argument), that must exist as part of the reals if defined as they are. But we've no example of them. They're jus…

It's not really a new idea though. I just don't think it is a particularly good one.

The cool thing about mathematics is that we can use finite reasoning to talk about things that are otherwise hard to grasp, and that are yet part of our shared reality. Saying that the reals don't exist is pretty much the same as saying that the natural numbers don't exist. After all, you are going to have a hard time to name each and every one of them. Oh, you say that countability makes a difference here? Well, that's a purely mathematical concept, and if you don't believe that mathematics is real, how are you going to convince me that this concept makes sense?

Post reply on HN