Questions tagged [computability]

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

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

1
2 3 4 5
35