Linked Questions

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
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
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
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
4 votes
1 answer
833 views

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
1 answer
932 views

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
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
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
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
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
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
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
0 votes
1 answer
121 views

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

15 30 50 per page