Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,677
questions
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
What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a
I'm given the following python function:
...
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 ...
