Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,571
questions
0
votes
0answers
18 views
Solving NP problems : analogy between the SAT problem and the shortest path problem
in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences),
whose purpose is to show how a SAT problem can ...
0
votes
0answers
23 views
A Turing machine for which it is impossible to predict whether it halts or not on a fixed input
The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
1answer
23 views
Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not
It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input.
My related question would be the following: is it true that for every fixed $M_0$ ...
2
votes
1answer
59 views
Halting problem for fixed Turing machine and fixed input
It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.
What if we fixed both the machine and the input? I.e., is it decidable for every ...
2
votes
1answer
31 views
How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?
After defining pushdown automaton in Sipser's book at p. 113:
at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following:
My question is about the part "...
0
votes
0answers
21 views
Is this a computable function? Is the reduction correct?
Let $A$ be a set, $K=\{x:\phi_x(x)\downarrow\}$. Let c to be a total computable function such that $\phi_{c(x,y,n)}(z)=\begin{cases}\phi_n(z) & \text{if }\phi_x(y)\downarrow\\\uparrow &\text{...
1
vote
1answer
63 views
Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable
Using 2SAT and implication graphs, how could I prove the following properties of implication graphs:
Suppose there is a directed path between literals l1 and l2 in G_φ. Then there is also a directed ...
0
votes
0answers
26 views
Improving binary recursion calculation
I am trying to write a program in Python for the infamous egg drop puzzle using recursion. In case you do not know the problem statement, here it is:
https://code.google.com/codejam/contest/dashboard?...
0
votes
1answer
65 views
show that this decidable set $C$ exists
I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $...
1
vote
3answers
47 views
NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution
The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.
My question is, ...
3
votes
2answers
235 views
show that in every infinite computably enumerable set, there exists an infinite decidable set
I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set.
As an attempt to solve the problem, I could only think of a proof by ...
0
votes
1answer
24 views
Determining recursive enumerability of given languages
I came across following problem:
$L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
$L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
1
vote
1answer
37 views
Mod 2 is primitive recursive
Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive.
My attempt is as follows
$$ E(x) = x \mod 2$$
To show that any function is ...
2
votes
2answers
320 views
Why doesn't the recursion theorem prove there is an undecidable finite set?
I created something similar to Sipser's proof for the undecidability of $A_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't figure ...
0
votes
0answers
35 views
Is there defined limits on, how a Turing Machine can emulate itself / another one?
Meaning for example lower or upper bounds of any kind, possibly concerning time or space complexity?
5
votes
1answer
48 views
Is there such a notion as “effectively computable reductions” or would this be not useful
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
2
votes
1answer
104 views
Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive
Question: Let $$S =
\{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape}
\}.$$ Show
that $S$ is r.e. (Turing acceptable) but not recursive ...
-1
votes
1answer
102 views
Showing on-line P = NP
I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations.
Following that, I ...
0
votes
0answers
51 views
How to show that a partial function is recursive?
I try to prove that this function is recursive:
$$f(x_1,x_2)= \begin{cases}
2x_1-x_2 & \text{if $x_1 \geqslant \sqrt{x_2}$} \newline
\bot & \text{otherwise}
\end{cases}$$
I think that I need ...
0
votes
1answer
27 views
simple question about epsilon and estimation turing machines
i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
0
votes
0answers
17 views
algorithm that finds minimal vertex cover of a given vertex
i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to.
not sure on how to do it correctly, ...
1
vote
1answer
32 views
What are HP and MP in this context?
From Kozen's Automata and Computability, 3ed, lecture 32 p. 328:
What are HP and MP in this context? I tried looking around and this text says:
How did the halting problem and membership problem ...
0
votes
1answer
22 views
Converting a function with single parameter to a function with multiple parameters
I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:
Given a string or a list, do an aggregation operation on each of its elements. Here ...
0
votes
1answer
46 views
How can i solve a recursion equation with square root using recursion tree method?
$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$
I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.
I just don't want to ...
1
vote
1answer
78 views
How to show that a $\log_2(x)$ is a recursive function?
I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as:
$$\log_2 (x)= \begin{cases}
y & \text{if $x=2^y$} \newline
\bot &...
0
votes
1answer
16 views
Reducing vertex cover to minimal vertex cover
What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?
Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
1
vote
1answer
51 views
Connection between vertex cover and P=NP
I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.
In an undirected graph $G(V,E)$, ...
1
vote
0answers
13 views
Applying the Parameter Theorem to show that a function is not computable
Show that $g: \mathbb{N} \to \mathbb{N}$ such that
$$g(x)=\begin{cases} 1 & \text{if halt}(2833,x) \\ 0 & \text{otherwise} \end{cases}$$
is not computable.
We know that
$$g(x)=\begin{...
1
vote
0answers
28 views
Obtaining a graph with no cycles after removing k edges
I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
0
votes
2answers
44 views
There are functions with f (n) = f (2n) which can't be calculated
I have to proofe that there are functions defined by $f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$, which are not-computable. However I'm not really sure about the correct ...
2
votes
2answers
90 views
Easy-to-describe example of uncomputable function
After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine. A curious philosophy ...
0
votes
0answers
16 views
Given a p.c. function $f(x,y)$ find a p.r. function $g(u,v)$ s.t. $\Phi_{g(u,v)}(x)=f(\Phi_u(x),\Phi_v(x))$
Since $f$ is p.c. we know there's a program $\mathscr{P}$ that computes it. Let $w=\#(\mathscr{P})$. We have:
$$f(\Phi_u(x),\Phi_v(x))=\Phi(\Phi(x,u),\Phi(x,v),w)$$
But the left hand side is a ...
2
votes
4answers
63 views
How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation?
Are the ones in modern programming languages equivalent to, say, Context-Free Grammars or is there an intermediate (between finite automata and CFGs) set of languages that it covers?
3
votes
0answers
35 views
Why does it take more than the original alphabet to generate sets of strings?
I am reading Computability by Nigel Cutland and I'm stumped on a brief statement about generating particular sets of strings that is not explained or given any examples.
First, here are some ...
2
votes
0answers
36 views
Proving inexistence of a PCOMPLETE language in log logarithmic space cannot exist
Hello and thank you for helping me understand the following:
I am trying to understand why the following cannot exist: A P-Complete language in regards to a log-logarithmic space.
context: Defining ...
1
vote
1answer
40 views
Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $
How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}.
My try:
Construct a ...
4
votes
1answer
62 views
why does $ A≤_p \#SAT$ if $A \in BPP$
hello and thank you for helping me understand the following:
I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$?
language A is in BPP class, if for a probabilistic turing ...
1
vote
0answers
16 views
Meaning of “uniformly computably enumerable in m”
Nies, in Computability and Randomness, p. 6, defines "uniformly computably enumerable":
A sequence of sets $(S_e)_{e\in\mathbb{N}}$ such that $\{\langle e,x \rangle : x \in S_e \}$ is c.e. is ...
2
votes
1answer
60 views
Is the following fuction computable?
I'm trying to show that $K_1 \le_1 K$ where $K$ is the diagonal halting set $\{x : \varphi_x(x) \downarrow\}$ and $K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$, then I defined the function
$$\...
0
votes
0answers
25 views
is the set of decidable language the same as the set of computable functions?
is the set of decidable languages the same as the set of computable functions? As well as the complement: is the set of undecidable languages the same as the set of uncomputable functions?
I feel ...
0
votes
0answers
14 views
how does the set of uncomputable functions relate to the set of non-halting programs?
How does the set of uncomputable functions / undecidable languages relate to the set of non-halting programs?
underlying: how do programs relate to functions?
-1
votes
1answer
42 views
Are non halting programs not computable?
Are non halting programs not computable? How are these two sets of programs related: is a non halting program just a specific example of a type of program that is not computable or is it technically ...
0
votes
1answer
33 views
What computational model supports arbitrarily sized integers?
I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
0
votes
0answers
35 views
Union of a decidable language with complement of a recursively enumerable language
So the question wants to prove or disprove that 'a Union of a decidable/recursive(i understand them to be the same) language and the complement of a recursively enumerable language is a recursive/...
0
votes
1answer
39 views
Can a computable program have an infinite output?
Can a computable program produce an infinite output from its (presumably finite) input?
*I wouldn't think so for similar argument as to why it can't compute over an infinite input.
A follow on (...
-1
votes
1answer
28 views
if there is no reduction from A to B
I'm facing the following question :
If there is no $𝐴\leq_𝑚𝐵$ reduction,
does this necessarily mean that A is not decidable?
for any choice of B.
thanks in advance.
3
votes
0answers
99 views
Undecidability of language involving two TMs
I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve.
Given $M_1$, $M_2$ Turing machines, is it true that for ...
0
votes
0answers
29 views
Use the Rice's theorem to prove that the following property of a Recursive Enumerable language L is undecidable
This exercise was taken from the book "Languages and Machines: An Introduction to the Theory of Computation" by Thomas Sudkamp. It refers to exercise 12 (b) chapter 12. Given a language L which is ...
3
votes
1answer
121 views
Compare two complexity functions having the same asymptotic complexity
For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:
$A1: T_{A1}(n)=4n^2 +7log(n^2)$
$A2: T_{A2}(n) = 4T(n/2) + log(n)$
Say, technically ...
0
votes
0answers
19 views
Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language
I have the following proof which I don't fully understand.
L D/ is the complement of the Diagonalizaton Language.
L U is the Universal language.
Assume U* is a TM for Lu which always halts. ...
