Linked Questions

4 votes
1 answer

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 ...
SebiSebi's user avatar
  • 143
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,935
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
18 votes
5 answers

How long does the Collatz recursion run?

I have the following Python code. ...
9bi7's user avatar
  • 305
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
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
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
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,435
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
9 votes
5 answers

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 ...
omega's user avatar
  • 553
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
9 votes
2 answers

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 ...
Quantum spaghettification's user avatar
6 votes
1 answer

Show that a language is decidable iff some enumerator enumerates the language in lexicographic order

The proof is given in the below: If $A$ is decidable, the enumerator operates by generating the strings in lexicographic order and testing each in turn for membership in $A$ using the decider. Those ...
Idonotknow's user avatar
5 votes
2 answers

Union of R.E. and Non R.E. language

Let \begin{align*} L_1 &=\{\langle M,w\rangle \mid M\text{ halts on }w\}\\ L_2 &=\{\langle M,w\rangle \mid M\text{ does not halt on }w\}\,. \end{align*} Here $M$ represents encoding ...
Zephyr's user avatar
  • 993
4 votes
3 answers

To what extent is my interpretation of computable numbers correct?

Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to ...
Chill2Macht's user avatar
8 votes
1 answer

If the Halting Problem was solvable, and we solved it, what would be its implications?

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved. What would be the Halting Problem's implications in today'...
Zaenille's user avatar
  • 191
0 votes
2 answers

Is P decidable?

It seems correct that any single given algorithm must either have polynomial runtime or not. Is there a specific algorithm that (does or does not actually lie in $P$, but) can neither be proven nor ...
heinzelotto'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
1 vote
3 answers

Why every finite set is computable?

According to wikipedia, every finite set is computable. Definition: set $S \subset N$ is computable if there exists an algorithm which defines in finite time if a given number $n$ is in Set. ...
Ayrat's user avatar
  • 1,075
2 votes
2 answers

Are functions with a finite domain and codomain always computable?

I apologise if my following reasoning is flawed, but I cannot find the "bug" in it. Consider two finite subsets of $\mathbb{N}$, namely $A$ and $B$. The set of all functions $f:A\rightarrow ...
olinarr's user avatar
  • 394
3 votes
2 answers

Is equivalence of CFGs decidable for finite sets of grammars?

Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and ...
user222's user avatar
  • 33
4 votes
1 answer

How to show that f(x) is primitive recursive?

Let $$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true }\\ 0 \quad \text{otherwise}\end{cases}$$ Show that f(x) is primitive recursive. I know a primitive recursive ...
Gigili's user avatar
  • 2,193
4 votes
2 answers

Is this language depending on P = NP recursive?

Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language $$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$ ...
alienCoder's user avatar
7 votes
1 answer

Undecidable vs Unsolvable?

In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is ...
Jenna Maiz's user avatar
5 votes
2 answers

Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
Joachim Breitner's user avatar
4 votes
1 answer

What's an intuitive distinction between semi-computable problems and noncomputable problems/functions?

The definitions I've found were highly technical and using terms I've never seen before. Say, I have a certain irrational number e that I get get closer and closer to with a computer and I want to ...
sdfasdgasg's user avatar
1 vote
2 answers

(Un)computability of a restricted Halting Problem

Before I start with my question, I want to state some notation I am using. I fix some arbitrary but fixed enumeration of Turing Machines (TMs) and denote with $\Phi_i : \mathbb{N}\to\mathbb{N}$ the ...
hetzi's user avatar
  • 131
2 votes
1 answer

Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?

The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific ...
user183748292's user avatar
2 votes
3 answers

Why is this language regular?

If you could include your thought process in determining why it's regular it would help me a lot. $L_1 = (0^*(10)^*11)$ $L_2 = \{ \langle M \rangle \mid M \text{ is a Turing machine that halts on all ...
AC9000's user avatar
  • 179
-1 votes
2 answers

If the “is P equals to NP?” is a NP-COMPLETE, what does it tell us?. Some conclusions?

If there is someone can prove that the problem "is P equals to NP?" is a NP-COMPLETE problem, what we can conclude from this?
user avatar
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
2 votes
2 answers

Is it possible to design a programming task that is unsolvable?

Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least ...
Daniel McIntosh's user avatar
1 vote
2 answers

Decidable problems for which no concrete decision procedure is known

I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. ...
Jason Hu's user avatar
  • 632
0 votes
1 answer

Some questions about the Computability of Turing Machines

I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines. Consider we have the partial functions $f,g,h,t: \mathbb{N} \...
katarina's user avatar
1 vote
1 answer

Why Right-Division of regular language with RE\E language is regualr?

I think I can't understand the meaning of language being decidable. The next case makes no sense to me: Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
Ella 's user avatar
  • 109
0 votes
1 answer

Do proofs of $HALT$'s undecidability make it clear that it's practically relevant?

The proof of $HALT$'s undecidability usually goes like this: we assume the existence of a halting decider and incorporate it into a machine $D$ that takes a TM as input, runs it on its own encoding ...
CuriosityScream's user avatar
2 votes
1 answer

Is a finite Solomonoff learner worse than human learning?

An elegant program for a bitstring is the shortest program on a universal Turing machine that outputs this bitstring. According to Kolmogorov complexity, the length of the elegant program is ...
yters's user avatar
  • 1,427
0 votes
1 answer

Reference for an undecidability proof [duplicate]

I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch". With "from scratch" I mean that it does not use some other undecidable problem to ...
Trylks's user avatar
  • 147
1 vote
1 answer

Does there exist a undecidable infinite language with only a finite undecidable subset?

I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an ...
orlp's user avatar
  • 13.6k
2 votes
1 answer

Decide if a language has a word of a given size

Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable: $$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ ...
Sam's user avatar
  • 23
0 votes
1 answer

Are there noncomputable functions with a finite search space? [closed]

The top rated answer to Why, really, is the Halting Problem so important? lists a few examples for a noncomputable problem. However, these mostly involve an infinite search space. Are there ...
Karsten's user avatar
  • 101
0 votes
2 answers

Why is $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ decidable?

I get that the argument for this set $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ to be decidable is that $|w|\leq7$ meaning it is a finite set and therefore it can be decided. ...
linuxxx's user avatar