Linked Questions

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
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
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
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
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
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.7k
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
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
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
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
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
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
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
64 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
  • 739
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
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
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,447
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
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
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
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
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
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
18 votes
5 answers

How long does the Collatz recursion run?

I have the following Python code. ...
9bi7's user avatar
  • 305
14 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,455
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
36 votes
9 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,159
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
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

15 30 50 per page