Questions tagged [computability]

Questions related to computability theory, a.k.a. recursion theory

Filter by
Sorted by
Tagged with
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?

1
2 3 4 5
36