Linked Questions

0 votes
1 answer
95 views

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
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
0 votes
2 answers
76 views

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

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

(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
86 views

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

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

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

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

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

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

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

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

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
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
  • 739
5 votes
2 answers
3k views

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

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

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

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
797 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 ...
SebiSebi's user avatar
  • 143
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
7 votes
1 answer
3k views

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

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
288 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
18 votes
5 answers
6k views

How long does the Collatz recursion run?

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

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