Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
31 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
15 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 ...
-1
votes
0answers
15 views

algorithm for a #SAT oracle (#SAT algorithm)

i tried to look for an algorithm that decides whether an input x is in #SAT or not. $\#SAT$ is defined, at least in this case to be: $<\phi ,k>=\left\{\phi \:is\:a\:boolean\:formula\:with\:at\:...
0
votes
0answers
16 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
votes
0answers
18 views

Finding an algorithm that after removing k edges we get an acyclic graph [duplicate]

Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k,...
0
votes
1answer
26 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
19 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
32 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
70 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
15 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
38 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
24 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
41 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
88 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
3answers
49 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
33 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
35 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
31 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
42 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
votes
0answers
21 views

Creating language $L_1$ with given parameter

Suppose $G$ is a context-free grammar, the language $L_0⊆\Sigma^*$ is also context-free but not-regular and $\#\not\in \Sigma$. Using $L_{(G)}$, $\#$, $L_0$, and $\Sigma^*$ create language $L_1$ such ...
-1
votes
0answers
22 views

On existence of simple sets [duplicate]

I want to prove that simple sets exist. I found similar question here, but it is about existence of immune sets. My progress so far: I understand the definition of a simple set (it is enumerable ...
1
vote
0answers
15 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
59 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
24 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
13 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
41 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
31 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
31 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
38 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
25 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
97 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
28 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
116 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
17 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. ...
0
votes
1answer
41 views

Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing ...
0
votes
1answer
27 views

In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
0
votes
0answers
11 views

Do $PR/Poly$ solve the halting problem of Turing Machine?

I know that $R/Poly$ solves the halting problem, as we can have the program that runs for longest time as advice and check which halts earlier. But what if we weaken the $R$ into something, like $PR$?
0
votes
1answer
32 views

Would models of computation in other conceivable universes be Turing complete?

I'm interested in gathering some references that discuss the topic of the relationship between computation and physics. Specifically, I'm interested in investigating two points of view: our current ...
1
vote
1answer
66 views

Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive?

Consider a Gödelian numbering of partial recursive functions. Consider the set of indexes corresponding to some function $\phi$. It may be seen that this set is not recursively enumerable. Does this ...
2
votes
2answers
90 views

Grammar with fewest variables

I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints. ...
1
vote
1answer
17 views

Is checking if the length of a C program that can generate a string is less than a given number decidable?

I was given this question: Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable? With respect to ...
0
votes
0answers
60 views

Restriction: polynomial time decision of instance is why needed to “decision Problem”?

I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)". (latest version is sixth.) There are some discriptions in this book that I don't understand Not all binary ...
0
votes
0answers
17 views

Proving the existence of a $\Pi_1$-sentence in True Arithmetic that is independent of Peano Arithmetic

I am trying to wrap my head around how to prove the following statement: There exists some $\Pi_1$-sentence $A$ such that $A \in \textbf{TA}$ but $\{A, \neg A\} \cap \textbf{PA} = \emptyset$. $\...
1
vote
2answers
43 views

Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph?

Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an ...
4
votes
1answer
70 views

Is there a model of ZF¬C where some program always terminates but has no loop variant?

Wikipedia has a proof that every loop that terminates has a loop variant—a well-founded relation on the state space such that each iteration of the loop results in a state that is less than the ...
5
votes
0answers
49 views

Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
2
votes
3answers
82 views

Are there any problems that reduce to the halting problem?

I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where ...
0
votes
0answers
33 views

Why does such reductions work [duplicate]

In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...

1 2 3 4 5 32