Hacker News Reader

Comment by wizeman | Hacker News Reader

> Deciding whether a finite Turing machine - a.k.a. a real computer - halts is EXPTIME-complete

Can you point me somewhere that proves this exact statement you're making? Or at least, explains why it is true.

I'm interested in reading about it.

I mean, assuming you are correct (and I have no reason to believe you aren't) it still doesn't guarantee that the problem is intractable (as EXPTIME-complete algorithms can still run very quickly in practice), but yes, I think it would suggest that it is intractable (for real-word applications).

View on HN

Let's see, I just looked that up before. Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps. This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit. So that seems a lot less worse then at first sight, but on the other hand this uses a terrible bound for the number of steps.

[1] https://cs.stackexchange.com/questions/112684/halting-proble...

[2] https://en.wikipedia.org/wiki/EXPTIME

> Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n bit of memory, therefore solving the halting problem for a machine with n bit is at least as hard as answering the question whether a Turing machine halts within n steps.

I'm following so far.

> This is in EXPTIME [1][2] given that the input n is encoded in log(n) bit.

Perhaps I'm reading this incorrectly, but these proofs seem to assume that you're simulating the machine running step by step?

Is it proven that the only way to solve the bounded Halting problem is by running the program step by step?

If not, it seems that this is only proving a high complexity bound (i.e. that the problem is not more complex that EXPTIME), not a low bound (i.e. that the problem can be solved in less complexity than EXPTIME).

Replied to the wrong comment.

https://news.ycombinator.com/item?id=33749430

Interesting, thank you! I am having a bit of difficulty understanding the exact implications in this context, but I will give it some thought.

Naively it seems not to bad to me but I am totally not an expert. If you have a million bits of state, we ask if a machine will halt in a million steps, otherwise we can not be sure that the machine does not use more than a million bit of memory. This of course heavily underestimates the hardness as you can have a machine with only 20 bit that goes through a million states. This also means that the EXPTIME is not that bad because the problem size is only 20, the number of bits required to write the number of bits in the machine, not the number of bits in the machine itself.

Here is a good article you might be able to understand that pretty much provides an answer to your question.

https://www.quantamagazine.org/the-busy-beaver-game-illumina...

No, it does not provide an answer. What does that have to do with analyzing a finite-state machine in EXPTIME-complete time?

The busy beaver problem, again, assumes it is running on a Turing machine with infinite memory.

Don't confuse a program defined using a finite number of states with a machine that can only have a finite number of states. It's just another example of the points I'm making about how a theoretical mathematical problem is an interesting curiosity and might even be an interesting problem to solve but it does not necessarily apply to the real world. And how everyone seems to think that this mathematical problem applies to programs running in real-world computers.

Someone else mentioned the busy beaver problem and I've given a more complete answer there:

https://news.ycombinator.com/item?id=33744326

Both people are me. I think there is an answer in that article, but I can’t unpack it for you. It explains why what you are asking about is so impractical, and can point you to topics to gain a better understanding.

In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its states. 64mb leaves a lot of room for unique states without a cycle.

> In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its states. 64mb leaves a lot of room for unique states without a cycle.

Why do you assume that you have to go through all the states of the program to determine whether it will run into a cycle?

The foundation of cryptography is that there exists algorithms in which the only way the beat them is to iterate over a computationally infeasible number of states to be able to decrypt something.

To not believe my assumption would require you to believe that such algorithms do not exist.

Agreed.

Since the assumption has not been proven, this is why the foundation of cryptography is still on a bit of a shaky ground, as none of those algorithms are proven to be unbeatable (the one-time pad being the exception, although it's not very useful in practice).

It's probably also why weaknesses in cryptographic algorithms are still being discovered every now and then, unfortunately.

It seems that your assumption is that there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts.

However, it is simple to show that this is at least as hard as NP complete. For instance, you can map the Hamiltonian cycle problem to a halting problem over programs that do an infinite walk on graphs without a Hamiltonian cycle and those that stop whenever they complete a walk along a Ham cycle.

At this time P vs NP is still wide open and, in general, statements in complexity theory are usually dependent on some unproven hypothesis so I still don't understand what is your point exactly.

Yes, exactly, you seem to be understanding my point: there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts.

Among other things, because the P vs NP issue is still wide open, yes.

I'd just like to add three more minor points:

1. Many people believe the above to be false, because they believe that the problem is undecidable also for programs with a bounded number of states.

2. That I would like if more people focused on finding such an efficient algorithm.

3. And that I think that even some people who believe that the problem is decidable think that it's impossible to have an efficient algorithm because of the Halting problem and Rice's theorem, which formally speaking, neither of them say anything about whether such efficient algorithms exist or not.

To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying.

The P vs NP question is open but the conditional results are not merely novelties. There are many results that show very weird consequences for having P=NP. So either the nature of computing is utterly bizarre or in fact there are many common problems which are simply impossible to solve exactly in a reasonable amount of time.

You can of course try to find good heuristics that cover some common cases or even approximations of NP hard problems in some cases. There are literally thousands of researchers doing that every day.

> To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying.

I hope you are correct :-)

> There are many results that show very weird consequences for having P=NP. So either the nature of computing is utterly bizarre or in fact there are many common problems which are simply impossible to solve exactly in a reasonable amount of time.

Wow, that's very interesting! Can you recall an example or two of such consequences? I would be really interested in reading about that.

Edit: Donald Knuth seems to believe that P=NP and also says there would be no major implications if we found such a proof...

> You can of course try to find good heuristics that cover some common cases or even approximations of NP hard problems in some cases. There are literally thousands of researchers doing that every day.

Completely agreed!

Perhaps you are right and my worries are unfounded.

Here is an interesting discussion about the relation to EXP and circuit complexity. https://mathoverflow.net/questions/58201/why-is-p-np-implies...

A nice presentation by Wigderson may also help to see consequences of P=NP in a less rigorous phrasing ("'Creativity' can be efficiently automated [if P=NP]"). https://view.officeapps.live.com/op/view.aspx?src=https%3A%2... There is a more formal text as well: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06....

Another class of results that I find interesting are inapproximability results. Namely, for certain NP hard problems, it is impossible to have a polynomial algorithm that computes the right value (for all instances) within a certain approximation factor unless P=NP. In https://dl.acm.org/doi/10.1145/1132516.1132612 Zuckerman shows that approximating MAX-CLIQUE is hopeless unless P=NP.

This is of course just a mountain of evidence and not a proof. It does mean that there are potentially many ways in which one could prove P=NP without necessarily achieving anything practical. This is what I think Knuth means: you could have a non-constructive proof of P=NP or perhaps an algorithm with complexity n^10^10^10 that solves an NP-complete problem.

Simulating it step by step is the upper bound establishing that is in EXPTIME, the second part, the reduction to the bounded halting problem, is what establishes EXPTIME-completeness. And the time hierarchy theorem finally establishes that EXPTIME is not equal to P.

Reply on news.ycombinator.com