Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,790
questions
1
vote
1answer
29 views
Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain
Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any
$L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why.
I think the claim is incorrect, and I'm trying ...
0
votes
1answer
59 views
Reduction from problem A to another problem B
I have a question from a test that I failed to pass, I failed to do the question.
The question:
Let A and B have two languages so that there is a reduction function f: $A\leq _pB$.
Suppose that $A \in ...
1
vote
2answers
46 views
Reduction between CLIQUE to SUBSET SUM
I have a question from a test that I failed to pass, I failed to do the question.
The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
0
votes
0answers
28 views
Reduction from IS problem to other problem [closed]
Given graph 𝐺 = (𝑉, 𝐸) it is said that it is a star if there is a vertex $𝑣_0 ∈ 𝑉$ so that all the other vertices are connected exclusively to it (and not to ...
2
votes
1answer
36 views
Reduction from language in P to another language in NP
I have a question I was unable to do, from a last test I had.
This is the question:
Will be $A \in NP$
Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
5
votes
1answer
79 views
Reduction from the SAT problem to the NAE-SAT problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
1
vote
2answers
117 views
edge-coloring and vertex-coloring reduction problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
Edge-Coloring problem, we get as input graph G = (V, E) and natural
number k and ask "...
0
votes
1answer
16 views
Reduction from the Clique problem to the Odd Clique problem
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question:
Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
31 views
Complications of a language that reaches a state of reject
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question
Let's look at the language $L_\mathrm{reject} = ${
$\left \langle M,w \right \...
3
votes
1answer
37 views
edge-coloring reduction problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
Edge-Coloring problem, we get as input graph G = (V, E) and natural
number k and ask "...
2
votes
1answer
33 views
Language in NPC and CoNP
A few days ago I had a test that I failed to pass, and it had a question that I failed to do.
the question:
given:
$A \in NPC$
$A \in CoNP$
Determine which of the following statements is correct:
$P\...
4
votes
2answers
107 views
tautology vs satisfiability
I had a test that I failed to pass, and it had a question that I failed to do.
This is the question:
Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
2
votes
1answer
65 views
Reduction from TSP to even TSP
I have a question from a test that I failed to pass, I failed to do the question.
The question:
Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight ...
2
votes
1answer
61 views
Complexity of the language that enters an infinite loop
A few days ago I had a test that I failed to pass, and it had a question that I failed to do.
This is the question
Let's look at the language $L_\mathrm{loop} = ${
$\left \langle M,w \right \rangle$ | ...
1
vote
1answer
21 views
Relationship between NP and CoNP
I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question
This is the question
Will be $A\in NP$
Suppose that $A\notin CoNP$. ...
3
votes
2answers
50 views
Reduction with CoNP and CoNPC
I have a question I was unable to do, from a last test I had.
This is the question:
Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$.
Determine ...
2
votes
1answer
21 views
Reduction with NPH
I have a question in complexities that I could not do.
There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$.
Determine which of ...
-1
votes
1answer
34 views
Reduction from SAT to 3SAT
a few days ago I had a test and could not pass it. This is a question I did not understand in the test.
Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
0
votes
1answer
26 views
Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$
Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$
I am trying to prove that $L$ is not in $RE$ by reduction ...
1
vote
2answers
121 views
Reduction from vertex-coloring problem to edge-coloring problem
A few days ago I had a test and could not pass it. This is a question I did not understand in the test.
We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
0
votes
0answers
16 views
Understand what this phrase is in the Turing
I had a test a few days ago and failed it. There was a question that was not clear to me.
This is the question:
For the purpose of describing the drawing on the tape of a Turing machine at each step ...
0
votes
1answer
26 views
How to know if language is in comp or np?
I'm new to the site.
I had a test a few days ago and failed it, I had a question I did not understand.
This is the question:
Let's look at the FALSE language: Collect all the verses P in the form of ...
0
votes
1answer
12 views
Reduction from 2 finite languages when one doesn't include epsilon and the other does
Just did a test about the subject that had the following question:
I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off.
$L_2$={ab,$...
1
vote
2answers
49 views
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ if
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ in case of:
$L_S\in RE$
$L_S\in R$
0
votes
1answer
46 views
Issues in the proof of $E_{TM}$ is Turing reducible to $A_{TM}$
First definition:
$A_{TM}$ = $\{ <M,w> | $M is a TM and M on w accepts$ \}$
Second definition:
$E_{TM} = \{ <M> |$ M is a TM and L(M) = $\phi \}$
Let $T^{A_{TM}}$ be an oracle Turing ...
0
votes
1answer
15 views
Complementary language of $L\notin RE,coRE$
I mean if $L'$ defined as $L'=\overline{L}$, when $L\notin RE,coRE$.
From the logic point of view it should be $L'\in RE \cup coRE$, isn't?
But it's not make sense for me, where am I wrong?
-3
votes
2answers
102 views
Is this solution for the Turing's “halting” problem correct?
I think that Alan Turing's solution for the "halting" problem might be wrong.
Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't ...
2
votes
1answer
49 views
Does MIP* = RE's major breakthrough mean quantum computers are more powerful than turing machines?
Henry Yuen's youtube comment on this video https://www.youtube.com/watch?v=HL7DEkXV_60 (should be one of the top comments) explains that with the help of quantum entanglement (or quantum computers), ...
2
votes
2answers
598 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 ...
0
votes
0answers
21 views
The role of diagonalization - asymmetry between TM and Recursion Theory
This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can.
First, here is an hypothesis: diagonalization is syatematically used to prove ...
0
votes
1answer
18 views
Oracle for LBA halting on some input
Assume we have an oracle that tells, given a linear bounded automaton, if there exists an input on which it halts.
Can we then solve the real halting problem (i.e. decide if a given Turing machine ...
4
votes
2answers
35 views
How do you express a floor / ceiling in the approximation factor of an approximation algorithm?
Intuitively I feel like this is a bit of a dumb question, and is probably related to my vague understanding of approximation algorithms and whatnot.
Suppose I have some minimisation problem $X$ where, ...
2
votes
1answer
50 views
Proving that there are more problems than solutions
I have doubts regarding a proof of the following theorem:
'Set of all problems' is larger than the 'set of all algorithms' (or set of all C programs).
Put rhetorically, the theorem says that there are ...
4
votes
1answer
66 views
Is there a $\Sigma^0_3$ variant of the halting problem?
In terms of the arithmetical hierarchy, the halting problem is known to be $\Sigma^0_1$-complete, and the so-called universal halting problem, is the problem of determining whether a given computer ...
-5
votes
3answers
189 views
Does the Linz Ĥ specify a computation that never halts when the embedded halt decider is a UTM?
When we hypothesize that the halt decider embedded in Ĥ is simply a Universal Turing Machine (UTM) does this define a computation that never halts when Ĥ is applied to its own Turing machine ...
0
votes
1answer
32 views
What are some problems that have higher degree of unsolvalbilty than $\Pi^0_2$-complete problems?
I'm looking for some problems that have higher degree of unsolvalbilty in term of arithmetical hierarchy that requires more than 2 quantifiers like $\Pi^0_3$ ,$\Pi^0_4$ etc.
-6
votes
1answer
211 views
Halting problem undecidability and infinitely nested simulation
Halting problem: In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and
an input, whether the program will finish running, ...
0
votes
1answer
36 views
How to prove that this language is not recursive enumerable?
I need to prove that the following language is not recursively enumerable, while its compliment is recursive enumerable:
$L := \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle $ M $\rangle$ does not ...
0
votes
1answer
26 views
How to prove that $L_{D}\leq L_{U}$?
I have the following two languages:
$$
L_{U}\triangleq\left\{ \langle M,x\rangle\,:\,M\text{ accepts }x\right\} ,L_{D}\triangleq\left\{ \langle M\rangle\,:\,M\text{ accepts }\langle M\rangle\right\}
$...
0
votes
1answer
18 views
If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$
Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^*$. I'm trying to prove the following theorem:
If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$.
If $L_2$ is non-trivial the ...
1
vote
0answers
10 views
Heuristics to transform a recursively enumerable set into a diophantine set
The class of recursively enumerable sets is equal to the class of Diophantine sets. Given a recursive function, is there a way to produce a diophantine equation such that the trace of calls to the ...
0
votes
1answer
42 views
Reduction of Turing-machine language
How to show that the following language is undecidable using reduction on the halting problem?
$L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$
When TM ...
0
votes
1answer
53 views
Reduction of the diagonalization language to the universal language
I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a ...
1
vote
1answer
19 views
Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?
One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in ...
-3
votes
1answer
30 views
Prove a language is not regular without pumping lemma [duplicate]
How can you prove that $L=\{a^n b^{2n} \}$ is not regular without the use of pumping lemma?
1
vote
0answers
31 views
Prove that characteristic function $f_w$ in write protected input turing machine behave as a 2FSA
Write protected input turing machine is a single-tape TM that cannot write on the input portion of the tape. I almost prove that these TMs can only recognize regular languages but i have a problem in ...
1
vote
1answer
27 views
How to prove that the reduction relation is not symmetric
I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show ...
1
vote
2answers
232 views
Why is there no “traditional”-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
Why is there no algebraic definition of algorithm besides recursive functions?
If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?
...
0
votes
1answer
89 views
A question on decidability
I have a homework question that is as follows:
L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P ...
0
votes
1answer
17 views
SAT and Polytime Reductions
If an algorithm for $SAT$ runs in $O(n^{\log n})$ time, and if $L$ belongs to $\mathsf{NP}$, is there an algorithm for $L$ that runs in $O(n^{\log n})$ time?
