Hacker News new | past | comments | ask | show | jobs | submit login

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.


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.


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: