Linked Questions

9 votes
2 answers
660 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
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
4 votes
3 answers
669 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
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
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
10 votes
3 answers
285 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
1 vote
3 answers
2k views

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
883 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
3 votes
2 answers
1k views

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
827 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
2 answers
374 views

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
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
5 votes
2 answers
218 views

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

15 30 50 per page