Linked Questions

182 votes
13 answers
67k views

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
26k views

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
11k views

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
15k views

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
9k views

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
5k views

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
3k views

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
7k views

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
6k views

How long does the Collatz recursion run?

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

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
7k views

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
15k views

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
2k views

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
414 views

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
286 views

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