Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,739
questions
-1
votes
1answer
13 views
|L(M)| <= 330 is not computably enumerable
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.
Why is {M : |L(M)| <= 330} not CE?
I can't seem to understand the logic why it is not CE, wouldn't ...
0
votes
0answers
23 views
Undecidability of an Intersection
1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable?
2)What if we replace L with the complement of L?
Either 1 or 2 is decidable and the other ...
0
votes
0answers
12 views
How to Plot Logistic Regression using Seaborn? [closed]
I am trying to plot logistic regression model but seaborn regplot does not worked. What should I do?
0
votes
1answer
29 views
Decidability of languages with dfa/turing-machines
For any alphabet and any natural number k, a language of strings at least k is decidable.
So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has ...
0
votes
1answer
14 views
Question regarding notation of a language decidability
$1.\: A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$
$2.\:A_{DFA} = \{\langle B \rangle \mid B \text{ is a } DFA \text{ that accepts input string } ...
5
votes
1answer
56 views
Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered?
Are the sets in each stage of the arithmetic hierarchy well-ordered, with respect to : $T-$reductions, or $m-$reductions?
It is something which I have been unclear with for a while (from a ...
-3
votes
1answer
30 views
Strings of length $n$ enumerated by Turing machine
If $E$ is an enumerator and $n$ is a natural number, we define $\langle E,n \rangle$ to be all strings of length $n$ enumerated by $E$. Is $\langle E,n \rangle$ recognizable? Is it decidable?
0
votes
1answer
22 views
Converse of (two sets are RE => their union is RE) doesn't hold?
E.g. union of an RE set and its complement (where complement set is not RE) is Sigma star, wich is definitely RE.
But what if you first attach to the beginning of elements in S with a #, and elements ...
-2
votes
0answers
26 views
Infinite jump of a language
Let $A(n)$ be the $n$-th jump of a set $A$ for any natural number $n$.
Define the infinite iteration of the jump, $A(\omega)$, as follows: $$ A(\omega) = \{ \langle m,n \rangle : m \in A(n) \}. $$
...
-2
votes
2answers
30 views
If $A$ is c.e.-complete then the join of $A$ and $A^c$ isn't c.e
Let $A\subseteq\{0, 1\}^∗$, and let $A^c = \{0, 1\}^∗ \setminus A$ be the complement of $A$. Prove: If A is $\le_m$-complete for CE, then $A$ join $A^c$ is neither c.e. nor co-c.e.
c.e --> ...
-4
votes
0answers
30 views
Classification of language of all words whose length is a perfect cube
L = {x belongs to {a, b} : |x| is a perfect cube }
What is the smallest class of that the following language belongs to, between decidable and recognizable?
$$
\{ x \in \{a,b\}^* : |x| \text{ is a ...
0
votes
1answer
57 views
TM decidability using pigeonhole principle
I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular,...
0
votes
0answers
33 views
Show that a set is reducible to another set
Consider an operator $+$ defined on $P(\mathbb{N})$ as follows
$$A + B = \{2x:\ x\in A\}\cup\{2x + 1:\ x\in B\}$$
Show that $A$ is $m$-reducible to $A+B$ and $B$ is $m$-reducible to $A+B$
As per the ...
13
votes
0answers
121 views
What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?
In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
1
vote
1answer
44 views
Prove/Disprove: NP is closed under “mixed” complexity
Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:
$\...
1
vote
0answers
34 views
Determining whether a language $L_{a}$ is recursively enumerable
I'm trying to determine whether a language $L_{a}$ is recursively enumerable, but first I'm having trouble deciphering the definition $L_{a}$ given the following question:
Given an recursively ...
1
vote
2answers
41 views
If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$
If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$?
My intuition says no, but I couldn't find a counterexample.
0
votes
2answers
44 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 ...
0
votes
1answer
39 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$ ...
-1
votes
1answer
65 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
26 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
31 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
74 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
41 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
59 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
81 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
35 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$
43
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
35 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
34 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
77 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
36 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
68 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
57 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
57 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
30 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
37 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
27 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
48 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
495 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
38 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
49 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
123 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 ...
