Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,725
questions
1
vote
0answers
20 views
Reduction between Parity-SAT and approximate counting
Consider two problems as defined here.
Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:
The number of satisfying assignments for $f(...
0
votes
2answers
29 views
Can the intersection two non-recursive sets be recursive? Prove it
I am still really new to compsci theory and some of the topics are really hard to understand. For this Problem I would think that say we have two sets A and B and they are both non-recursive.
If we ...
-4
votes
0answers
31 views
Prove that $f(L)=L_{\Sigma^*}$
When:
$f(L)=\{f(x) | x\in L\}, L\in R$
$L_{\Sigma^*} = \{\langle M\rangle | L(M)=\Sigma^* \}\notin RE$
and
$\langle M_{\Sigma^*}\rangle$ is TM that accept straight away.
For:
$f(\langle M\rangle)=\...
0
votes
1answer
35 views
Vertex cover of minimal graph
I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
-2
votes
0answers
44 views
$\forall A\notin RE$ prove that $L_A =\{\langle M\rangle : |A\cap L(M)|\ge10 \}\notin RE $
My solution for this question is:
Reduction from $L_A$ to $A$, in the following way $f(x)=\langle M_x\rangle$
Emphasis: $\exists$ 10 different words $w_1 ,\dots,w_{10}\in A$, otherwise $A$ finite $\...
-1
votes
1answer
63 views
For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$
The $\Leftarrow$ direction is straightforward.
On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it.
For NTM, Non Deterministic Turing Machine, $M$, for ...
0
votes
1answer
23 views
Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$
When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa.
I'm thinking that this equal to $P=NP$, but I saw a solution (...
1
vote
0answers
27 views
For what reason this function is recursive primitive?
Let $\forall n \in \mathbb{N}\ \ P(n)$ a primitive recursive predicate such that $\neg P(n)$ for a finite number of values of $n$.
Why this function:
$$
f(x) =
\begin{cases}
1 & \text{ if there ...
1
vote
1answer
70 views
Why is $\forall x \in \mathbb{N}\ \Phi(x,x)$ unary but $\Phi$ is binary?
May anyone explain me why $\forall x \in \mathbb{N}\ \Phi(x,x)$ is unary but $\Phi$ is binary?
In my latest exam I wrote that the universal function $\Phi^n(x_1, x_2, ..., x_n,y) = \psi^n_y(x_1,x_2,......
1
vote
2answers
40 views
Turing machine that checks whether a given string is an output of a given machine and input
Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$?
My ...
0
votes
1answer
58 views
Minimum absolute value of subset sums of integer values
$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$
How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?
When $\...
2
votes
2answers
77 views
Why can't we compute the lexicographically-least word of a given length on which a given TM halts?
I had this question in my exam. but my answer is wrong(I didn't receive explanations why...)
$$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \...
1
vote
1answer
34 views
Why every finite language is polynomial?
I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$
42
votes
11answers
9k views
Can a computer determine whether a mathematical statement is true or not?
I was reading Introduction to the Theory of Computation by Michael Sipser and I found the following paragraph quite interesting:
During the first half of the twentieth century, mathematicians such as ...
-4
votes
1answer
40 views
Proof of existence of $L\in R\setminus P$
I saw some proof but I didn't understood it, any simple one?
1
vote
1answer
28 views
$\overline{SAT}$ vs. $UNSAT$, Is it the same?
I know this question may look stupid, but still..
Is the meaning of both "have no satisfiable assignment"?
0
votes
1answer
34 views
Deteremine if Language is in $R$ or $RE$
$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$
Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.
My ...
0
votes
1answer
32 views
$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$
I'm trying to understand why:
$$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$$
As I see it TM, $\langle M\rangle$, should accept all the inputs, and if one of the inputs rejected it's ...
3
votes
1answer
69 views
How can primitive recursion be a special case of minimization?
In several posts on StackExchange and elsewhere, I have seen claims that you only need to show you can construct constants, successor, projection, composition, and minimization to prove a language ...
1
vote
1answer
35 views
Computability of function composition
I have some problems to understand computability and hope you can help me.
In the lecture we had following problem:
Consider the three partial functions $f,g,h\colon N \to N$, where $f$ is computable ...
0
votes
1answer
26 views
Condition to prove $f$ is a reduction
A theorem says if $f$ is a computable function and we can prove $x \in A \Leftrightarrow f(x) \in B$, then we can use reduction so $A \leq_m B$.
But i'm confused if should I prove if :
$(x \in A \...
0
votes
1answer
51 views
Complementary for $SAT$
I have tried to find a definition of complementary language to $SAT$, I mean $\overline{SAT}$.
But I still confused, in case of $L\in \overline{SAT}$ is it mean:
if $\varphi\in L$ then all ...
-2
votes
2answers
65 views
Recursively enumerable notation $RE$ vs. $RE\setminus R$
I know that it's a bit stupid question.. , but still,
Is there any difference between $RE$ and $RE\setminus R$ notations?
I'm asking because I saw that in some places using both of the notations, for ...
0
votes
1answer
54 views
CookāLevin theorem and reduction as injective function
I saw that the injectivity "derives directly from the theorem", but i can't see how it's happen, any explanation?
3
votes
1answer
56 views
Characterization of computationally universal functions
Is it correct to state that $u$ is a universal function if and only if
$$
\forall f : \text{RE} \quad
\exists g : \text{R} \quad
\exists h : \text{R} \quad
f = h \circ u \circ g
$$
where RE is the set ...
0
votes
1answer
39 views
For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$
I'm trying to understand what's the difference between $S=\emptyset$ and $S=\{\emptyset\}$
The diffenition that I found for $L_S=\{\langle M\rangle\ | L(M)\in S \}$
I understood that $S=\emptyset$ and ...
1
vote
1answer
28 views
A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)
I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'):
...
0
votes
1answer
36 views
How does CNN deal with rotation invariant pictures?
I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply ...
0
votes
0answers
26 views
Is my assumption about non trivial propery correct?
"make sure you understand why for a non trivial property $S$, $\bar{S}$ is also non trivial"
My assumption is: $S$ is non trivial property: There are L1,L2 such that $L_{1},L_{2}\in RE$ and ...
0
votes
1answer
47 views
Is a language recursive? 2 wrong ways of solving
Let's define:
$Disagree(M_1,M_2) = \{x| $The result of $M_1$ on $x$ different from the result of $M_2$ on $x\}$
that means: if $M_1$ accept, $M_2$ reject and vice versa
$NPA=\{L|\exists M_1,M_2$ ...
1
vote
2answers
488 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 ...
0
votes
2answers
35 views
For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$
It's claim 1 from Bader Abu Radi's solution to this question.
My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
*...
2
votes
2answers
53 views
State whether the language is in $R$, $RE$, etc. The intuition for the solution
I saw the solution but can't understand the intuition of the following question:
Let's define
$$L^{\ge k} = \{w\in L : |w| \ge k\}$$
and
$$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^...
0
votes
1answer
37 views
Reduction from $A$ to $B$ as execution of Turing machines
As explained in answers to this question, reduction from $A \le B$ can be represented in the following way.
But in this example:
from here
At least as I understand it:
The reduction is from $\...
2
votes
2answers
47 views
Is it valid to make an admission of a topological space by a “partial quotient map”?
It is well-known that the SierpiÅski space, $\{F,T\}$ endowed with topology $\{\emptyset, \{F\},\{F,T\}\}$, is admissible. I tried to implement it in Haskell.
First I implement $\mathbb{N}$ (including ...
1
vote
0answers
120 views
How can I simulate nested WHILE loops in a theoretical programming language to show Turing completeness?
PRE-WORK-POST is a theoretical programming language with the following structure, where P,Q and R are LOOP program:
$$\text{PRE} \ P \ \text{WORK} \ Q \ \text{POST} \ R \ \text{END}$$
First $P$ is ...
1
vote
1answer
37 views
Is there a connection between the Undecidability Theorem and “software complexity”?
I was reading Complexity: The Emerging Science at the Edge of Order and
Chaos and a certain passage got me really intrigued. When discussing
Chris Langton's explorations of artificial life algorithms,...
4
votes
1answer
57 views
Explain the difference between Turing Complete and Turing Equivalence
I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.
A computational system that can compute every Turing-computable
function is called ...
1
vote
1answer
31 views
Computable Functions
I'm learning about computable functions. Our definition for computable function is as follows:
Informally, a computable function is a function f : A ā B such
that there is a mechanical procedure for ...
1
vote
4answers
105 views
If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?
Suppose there is a polynomial time reduction from problem $A$ to $B$.
Why is the following false?
If $B$ is NP-hard then $A$ is NP-hard.
Can some explain this intuitively?
2
votes
2answers
33 views
If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$
I found the following question with an answer here, but I can't understand the steps of the solution.
Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive.
Solution....
2
votes
0answers
179 views
Is the While programming language with bounded number of variables Turing complete?
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
...
0
votes
1answer
32 views
De morgan's law in formal language
I found in some exercise in computation the following step:
I can't understand why is it equal terms, based of what I know about De morgan's law:
OR should be replaced by AND
where $w=\varepsilon$ ...
0
votes
1answer
69 views
How this language belong to R?
Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$} \}$$
I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
6
votes
5answers
3k views
I'm trying to understand why every language has an infinite number of TMs that accept it
I found the following answer:
$L_{17} = \{ \langle M \rangle \mid \text{$M$ is a TM, and $M$ is the only TM that accepts $L(M)$} \}$.
R. This is the empty set, since every language has an infinite ...
0
votes
0answers
13 views
Inverse VR-Vision, theoretical possibilities and the additional requirements
When using VR-Vision for looking around and the vision is from some point of interest, the look-around is a rotation from inside that point and it reqires a record of a 360° photo or a 360° camera ...
0
votes
1answer
39 views
Is the decision problem, for a Turing Machine are there any input strings rejected decidable?
Given a Turing Machine T, are there any input strings rejected by T. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it.
...
2
votes
2answers
40 views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
-2
votes
1answer
73 views
How does one sketch a proof to show that the following problem is in the P Complexity Class?
I have the following problem. I do not know where to start or how I should approach this problem. I am not sure about how to prove if a problem is in a complexity class of P . I know how to do NP but ...
1
vote
1answer
35 views
PCP when upper and lower words have different length
The Post correspondence problem (PCP) asks, given two sets of words $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ over the same alphabet, whether there are indices $i_1,\ldots,i_s \in \{1,\ldots,n\}$ and $j_1,...