566 views

### Finite languages are Turing decidable - contradiction [duplicate]

Let's say that I define the language $L$ over the alphabet $\{0, 1\}$ to be a language containing only one word, $w$, where:  w = \begin{cases} 1 & \text{if the continuum hypothesis is ...
56k 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 ...
23k 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, ...
7k 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. ...
12k 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 ...
8k 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,...
5k views

### How long does the Collatz recursion run?

I have the following Python code. ...
4k 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 ...
5k 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 ...
6k 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 ...
8k 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 ...
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 ...
22k views

### How to tell if a language is recognizable, co-recognizable or decidable?

If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable? Basically any hints or tricks that can be used to tell. Or maybe the ...
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 ...
### Are there any problems in $P$ which we do not know any $P$ algorithms?
A problem in $P$ is one that can be solved in polynomial time (or faster) on a deterministic Turing machine. Now if I am correct, there is nothing here referring to the algorithms - which can ...