Linked Questions

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 ...

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 ...

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, ...

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. ...

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 as ...

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,...

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 \{...

I have the following Python code. ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...