Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
19 views

DNF and CNF and Complexity Theory

$F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$. If that case is true and the conditions ...
0
votes
0answers
6 views

In the PCP, can we remove all dominos with the same top and bottom strings and still get a match?

Suppose we have an instance P of the PCP, and there exists a match for it. I am wondering if we remove all dominos that has the same string on the top and bottom, would there still be a match? My ...
1
vote
2answers
105 views

What does an admissible numbering of computable functions look like?

I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions. Initially my take on such an enumeration was from the point of view of an ...
1
vote
1answer
26 views

Relative primality is primitive recursive

How do I prove that the predicate $P(x , y)$ is primitive recursive, where $P(x,y)$ holds if $x,y$ are relatively prime?
0
votes
0answers
13 views

AMBIG_NFA decidability problem

As suggested by the title, $AMBIG_{NFA}$ consists of descriptions of all NFAs that accept some string along two computation branches. The original question is to show that it's decidable. Although I'm ...
0
votes
0answers
51 views

Is this set Recursive or Recursively Enumerable?

The set $Odd$, is the set of all $odd$ natural numbers ($N$). {1,3,5,7,...} Consider a set: $Z = \{ j \mid Odd \subseteq range(\varphi_j)\}$ $j$ is a number (code of program) for the function $\...
-1
votes
0answers
33 views

How can we tell a busy beaver candidate can halt?

If the BB function is computable, does that mean we know how to compute {i | program i eventually halts when run with input 0}, which is a clear contradiction with halting problem. Does this proof ...
-3
votes
0answers
19 views

finitely many distinct partially n-computable unary functions

A unary function f(x) is said to be partially n-computable if it is computed by some S program P such that P has no more than n instructions, every variable in P is among X,Y,Z1,...,Zn and every label ...
-1
votes
1answer
15 views

Use the diagonal method to prove that there is a total function from N to N which is not computable

I'm really not sure how to approach this problem.
0
votes
0answers
30 views

Prove that $A \oplus B$ is recursive if $A$ and $B$ are recursive

Let define $A \oplus B = \{2x \mid x \in A\} \cup \{2x + 1 \mid x \in B\}$. Prove that $A \oplus B$ is recursive if $A$ and $B$ are recursive. I am currently having the following idea. Since $A$ is ...
-2
votes
0answers
12 views

Turing Machine Encoding Legth

Given a problem of Turing Machine, the problem specified the length of encoding turing machine as less than $n$. What are the things that can be inferred from the encoding length of turing machine in ...
-1
votes
0answers
27 views

How to generally solve a graph problem with closed semiring?

I need some help with the problem below: Given a directed graph G, each edge is labeled by an element of some closed semiring. [Definitions] The label of a path is the product of the labels of the ...
-2
votes
0answers
27 views

Implementation-level description of a TM

I have the following TM that I'm not sure how to implement: Given $0^i$#$0^j,$ outputs $1^{i\bullet j}$ (output the number $i\bullet j$ in unary representation). How can I give a description this ...
0
votes
0answers
33 views

Solve recursive function $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$

In one of my college assignments, I came up with the following recursive function which I'm asked to solve: $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$ I tried a change of the variable or the ...
1
vote
1answer
28 views

Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

in one of my college assignments i came up with the following recursive function which I'm ask to solve: $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$ I could not use master method on it and it ...
0
votes
1answer
36 views

Are all $\Sigma^0_1$ sets of infinite sequences infinite?

I think I figured out some things about $\Sigma^0_1$ and $\Pi^0_1$ in the arithmetical hierarchy, for sets of infinite sequences, and I'm hoping I can get confirmation that I'm right, or can ...
0
votes
0answers
60 views

Halting problem. Decider “recognising itself” in the input?

This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the ...
1
vote
1answer
46 views
2
votes
2answers
125 views

how does Kleene-Post show two languages that are not Turing reducible to each other?

I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument. I've seen ...
3
votes
1answer
38 views

Can any computably enumerable set be generated by a prefix-free set?

Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the ...
1
vote
1answer
45 views

Why is universality of CFG undecidable?

Let $\text{ALL-CFG} = \{\left<G\right> \mid G\text{ is a CFG and } L(G) = \Sigma^*\}$. I have understood the proof of ALL-CFG is undecidable, but I wonder why the following proof is not ...
0
votes
1answer
33 views

Functional Abbreviation for Inst Expression in Turing's 1936 Paper

In Turing's 1936 paper On Computable Numbers Page 30-31, and its Correction Page 1-2 : For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l ) $ means that if $M$ scans symbol $S_j $ under $m-...
0
votes
0answers
36 views

Context-Free Grammar Question

Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0. Find the cfg for this expression. Here is what I tried to do: s -> AsB A -> 01 B -> 0 But then a language could be ...
0
votes
2answers
100 views

Is the halting problem pointless?

Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot ...
0
votes
0answers
97 views

Prove for Rice’s Theorem(Is the reduction used ? )

I was reading formal proof of Rice theorem in wikipedia: https://en.wikipedia.org/wiki/Rice%27s_theorem#Formal_proof I want to know is what we used here is the reduction algorithm : we reduce the Halt ...
0
votes
1answer
88 views

Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$

I need to find a Turing machine that decides $A=\{0^{3^n} | n\ge 0\}$. I tried doing the same as Sipser does on page 172 in his back, where he creates a Turing machines that decides $A=\{0^{2^n} | n\...
0
votes
1answer
59 views

Unary function is partially n-computable

Please help me prove the following problem: A unary function $f(x)$ is said to be partially $n$-computable if it is computed by some $\mathcal{S}$ program $\mathcal{P}$ such that $\mathcal{P}$ has no ...
1
vote
1answer
124 views

How to convert regular expression to CFG?

How can I convert the regular expression (ab*)*b to a context-free grammar? When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of ...
1
vote
1answer
20 views

How to show a function is primitive recursive by induction?

I know, loosely speaking, if we can define a function $f$ in term of \begin{align} &f(0,\vec{x})=g(\vec{x})\\ &f(n+1,\vec{x})=h(f(n),n,\vec{x}) \end{align} where functions $g,h$ are primitive ...
3
votes
2answers
80 views

How can I compute logarithm when comparison is undecidable?

In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively: ...
1
vote
2answers
35 views

Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages? I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and ...
1
vote
1answer
28 views

Proof that languages are Turing-recognizable iff computably-enumerable

A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes. In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
1
vote
2answers
24 views

Can you say anything interesting about a language knowing only that it is prefix-closed?

Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$). Knowing only ...
0
votes
0answers
22 views

Which function results from primitive recursion of the functions g and h?

Which function results from primitive recursion of the functions $g$ and $h$? $f_1=PR(g,h)$ with $g=succ\circ zero_0, h=zero_2$ $f_2=PR(g,h)$ with $g=zero_0, h=f_1\circ P_1^{(2)}$ $f_3=PR(g,h)$ with $...
1
vote
1answer
59 views

Why, intuitively, does the Ackermann function require $\mu$-minimisation?

I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive ...
6
votes
0answers
521 views

What could we say about that conjecture that yields P != NP?

Let $F$ be the set of all Boolean formulae. We say that a Boolean formula $\varphi$ is positive (=monotone) if $\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
2
votes
1answer
34 views

algorithm for checking satisfiability

In order to prove that SAT is in NP, I need to come up with a polynomial time verfier (an algorithm). The Cooks Levin Theorem uses a non-deterministic Turing machine but that's not what I am looking ...
1
vote
1answer
78 views

Church–Turing thesis and infinite Turing machines

What exactly is the definition of church turing thesis? It's really confusing. I want to prove the following statement: A Turing machine with infinitely many states is more powerful than a regular ...
3
votes
1answer
195 views

Does the term “continuity” have a different meaning in maths and in CS?

I ask this question because of some statements in the question "What is the 'continuity' as a term in computable analysis?" making me suspicious. I'm engineer, not computer scientist, so I ...
3
votes
2answers
515 views

What is the “continuity” as a term in computable analysis?

Background I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the ...
0
votes
2answers
47 views

what is the relevance of computability when applying diagonallization?

When thinking about diagonalization, I've always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter? Say for example, that have an enumeration of ...
-2
votes
1answer
46 views

running RAM on a given input

I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance, there's a Random Access Machine which has an input {0,1}*. The ...
0
votes
1answer
44 views

change turing machine to RAM

How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into ...
0
votes
1answer
41 views

For an NFA, can we always find a RAM?

For an NFA, can we always find a RAM, which recognises the same language?
1
vote
0answers
43 views

How do you write a python\pseudo code that generates all pair permutations?

What would be a good pseudo code or Python 3 code for the following permutations problem? Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and ...
0
votes
1answer
94 views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
2
votes
0answers
48 views

Inhabitation of STLC is in PSPACE

Urzyczyn: Inhabitation in Typed Lambda-Calculi (A syntactic approach) gives a proof that STLC inhabitation problem is in PSPACE (section 2, lemma 1). I don't understand certain aspects of the proof: ...
0
votes
1answer
100 views

Undecidability of the language of PDAs that accept some ww

I'm trying to solve problem 5.33 from Sipser's Introduction to the Theory of Computation, "Consider the problem of determining whether a PDA accepts some string of the form $\{ww|w\in \{0,1\}^∗\}$...
1
vote
0answers
54 views

If $A\in RE $ then $f(A)\in RE$

Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$. I can't figure out why this is true. Since $f$ is computable there is a Turing machine ...
1
vote
0answers
53 views

Mathematical limits on lossless data compression

Let's say Bob wants to send a particular binary sequence to Alice. Imagine that Bob and Alice both have powerful machines but slow Internet connections. Bob could just send the sequence directly but ...

1
2 3 4 5
34