Linked Questions

182 votes
13 answers

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
Brent's user avatar
  • 2,553
63 votes
6 answers

If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, ...
pafnuti's user avatar
  • 729
36 votes
8 answers

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
MaiaVictor's user avatar
  • 4,137
35 votes
6 answers

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
Tim's user avatar
  • 4,945
32 votes
5 answers

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter,...
thomas's user avatar
  • 421
26 votes
4 answers

Is the halting problem decidable for pure programs on an ideal computer?

It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems ...
Jules's user avatar
  • 632
22 votes
3 answers

Is there an algorithm that provably exists although we don't know what it is?

In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it. I am looking for similar results in computer ...
Erel Segal-Halevi's user avatar
19 votes
3 answers

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
user5507's user avatar
  • 2,191
18 votes
5 answers

How long does the Collatz recursion run?

I have the following Python code. ...
9bi7's user avatar
  • 305
18 votes
5 answers

Regular languages that seem irregular

I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated. So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{...
user6767509's user avatar
17 votes
5 answers

Are there any compression algorithms based on PI?

What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence). I've seen recently some prototype of πfs which assume that every file ...
kenorb's user avatar
  • 275
13 votes
2 answers

How to prove P$\neq$NP?

I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point. We can show that P $=$ NP if and only if we can design an algorithm that solves any ...
padawan's user avatar
  • 1,445
11 votes
3 answers

How to feel intuitively that a language is regular

Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular? I could use pumping lemma but some guys are saying just looking ...
doniyor's user avatar
  • 243
11 votes
1 answer

Is a function looking for subsequences of digits of $\pi$ computable?

How can it be decidable whether $\pi$ has some sequence of digits? inspired me to ask whether the following innocent-looking variation is computable: $$f(n) = \begin{cases} 1 & \text{if \(\bar ...
Gilles 'SO- stop being evil''s user avatar
10 votes
3 answers

Constructive version of decidability?

Today at lunch, I brought up this issue with my colleagues, and to my surprise, Jeff E.'s argument that the problem is decidable did not convince them (here's a closely related post on mathoverflow). ...
G. Bach's user avatar
  • 2,019

15 30 50 per page