Questions related to computability theory, a.k.a. recursion theory
2
votes
1answer
50 views
Where am I wrong?: “countability” and “recursive enumerability”
I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong ...
3
votes
1answer
68 views
Are these languages RE? How would I determine this?
Are these languages recursively enumerable?
$L = \{ \langle A\rangle \mid x\in L(A)\implies |x|\leq 13\}$
$L = \{\langle A\rangle \mid L(A) \subseteq \overline{L_{\mathrm{uni}}}\}$, where ...
0
votes
0answers
36 views
The complement of the acceptance problem reduces to the acceptance problem: ${A_{TM}}{ \le _M}\overline {{A_{TM}}} $ is this claim true?
If ${A}{ \le _M} {{B}} $ then $\overline A { \le _M}\overline B$ since the mapping reduction function is computable.
So, if ${A_{TM}}{ \le _M}\overline {{A_{TM}}} $ then $\overline{A_{TM}}{ \le _M} ...
5
votes
2answers
73 views
Computation of busy beaver function
The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n>4$? What is so ...
0
votes
0answers
35 views
How to write register machine code for Fibonacci [duplicate]
I am not sure whether this is the right place to ask this question, but since it involves register machine and computability, hopefully this is the right place.
I have tried to post on Programmers ...
3
votes
1answer
51 views
Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?
BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running ...
0
votes
1answer
93 views
A variant of the halting problem
Show that the problem of deciding, for a given TM $M$, whether $M$ halts for all inputs within $n^2$ steps ($n$ is the length of the input) is unsolvable. You can use the fact without proof that the ...
3
votes
2answers
86 views
Please explain “decidability” and “verifiability”
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".
I have done a reasonable amount of searching and going through the various texts I can put my hands on. ...
0
votes
2answers
35 views
Algorithm for difference of two semi-decidable languages
I have two algorithms
Algorithm 1:
if( Condition1(input)==true )
print(input);
else
loop forever;
Algorithm 2:
...
2
votes
1answer
49 views
Confusion related to time complexity of dynamic programming algorithm for knapsack problem
I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming
I didn't get how the time complexity of the algorithm came out to be ...
0
votes
2answers
67 views
Each of the two sets is recursively enumerable given their cartesian product is
$A \times B$ is an r.e. set, I want to show that $A$ (or $B$) is r.e.
4
votes
2answers
80 views
Is there an always-halting, limited model of computation accepting $R$ but not $RE$?
So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages.
I'm wondering, is ...
3
votes
1answer
49 views
What does it mean to say that a language is “effectively closed” under an operation?
I've been reading some formal language theory papers, and I've come across a term that I don't understand.
The paper will often refer to a set being "effectively closed under intersection" or other ...
3
votes
2answers
105 views
Show that it is undecidable if two Turing Machines accept the same language
I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a ...
4
votes
1answer
62 views
Computability of Kolmogorov Complexity
Fix a universal Turing machine $M$.
Let $A^*=\{0,1\}^n$ be the set of all binary string of length $n$.
Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$.
Just for a matter of ...
1
vote
1answer
28 views
The choice of programming language and the length of a program
I wonder how it's possible that:
it can be shown that all reasonable choices of programming
languages lead to quantification of the amount of absolute information in
individual objects that is ...
3
votes
1answer
26 views
Upper bound on register machine contents
I am doing some work on register machine theory which revolves around a 2-register register machine and attempting to show that it is not possible to compute an upper-bound on the final contents of ...
3
votes
0answers
67 views
How to eliminate for/if/while from algorithms when it's possible
Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive ...
2
votes
1answer
70 views
Is there a name for complement of recursively enumerable set?
If there is a recursive function
$$
f(x) =
\begin{cases}
1 & \text{if $x \notin A$}\\
\text{undefined} & \text{if $x \in A$}\\
\end{cases}
$$
Is there a special name for the class of sets ...
4
votes
3answers
124 views
Does our PC work as Turing Machine?
Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have ...
2
votes
3answers
86 views
How to tell if a language is recognizable, co-recognizable or decidable?
If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?
Basically any hints or tricks that can be used to tell. Or maybe the ...
1
vote
2answers
72 views
Show the problem of a machine visiting infinitely many tape cells on some input is undecidable
I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$?
I am considering a reduction from the ...
2
votes
1answer
61 views
Proving ALLTM complement not recognizable
A few definitions..
$$
\begin{align*}
\mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\}
\\[2ex]
...
1
vote
2answers
80 views
Introduction to complexity and computability
I'm looking for a good book that explains these subjects in a readable way.
Any suggestions ?
I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr ...
0
votes
1answer
45 views
Why isn't set $\{ \langle i, j \rangle \mid W_i = \overline{W_j}\}$ a recursively enumerated set?
Why isn't the set $\{ \langle i, j \rangle \mid W_i = \overline W_j\}$ a r.e. set?
Note: $W_x = L(M_x)$
4
votes
1answer
55 views
Prove that the Language is Recognizable
I got stuck on this question while studying for final exam.
I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.
1
vote
1answer
68 views
Is the intersection of two context free languages recursively enumerable?
I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.
I could not, however, find a citation for this quotation (and ...
1
vote
1answer
37 views
Have I got the right understanding of the mu operator?
I have a homework problem that says:
For $g(x,y)=xy-5$ compute $h(x) = \mu y(g(x,y))$ and determine its domain.
I was under the impression that this means the least y such that $g(x,y)=0$, so then ...
2
votes
3answers
57 views
What does it mean to say that there doesn't exist an algorithm from a TM point of view?
A TM for a recursive language corresponds to our informal notion of an algorithm.
as per Automata Theory, Languages and Computation by Ullman et al. Then there are languages called RE and $L_d$, ...
13
votes
3answers
217 views
What are common techniques for reducing problems to each other?
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
3
votes
1answer
70 views
Why the name Recursively Enumerable and Recursive?
Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?
2
votes
1answer
79 views
Does Turing Machine divergence depend on the input?
If there is a Turing Machine $M_e$ (computing some partially computable function $f$), is there an algorithm to decide if $f$ diverges for all possible inputs?
4
votes
1answer
116 views
How to show that a function is not computable?
I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
5
votes
1answer
63 views
Deciding if a Turing machine has made a left move
In writing a decider for a machine to see if it has made a left move or not on an input of w, it is said that if we continue the computation for $|w|+N+1$ ($N$ : number of states) number of steps, we ...
3
votes
2answers
118 views
Why isn't the class of Turing-Recognizable languages closed under Complement?
I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations ...
2
votes
1answer
100 views
Is every regular language Turing-decidable, and how can we prove this?
I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?
5
votes
3answers
130 views
Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?
Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of ...
10
votes
1answer
257 views
Can a Turing Machine decide if an NFA accepts a string of prime length?
I want to know if the following problem is decidable:
Instance: An NFA A with n states
Question: Does there exist some prime number p such that A accepts some string of length p.
My belief is that ...
0
votes
1answer
71 views
Can I use infinite numbers in a reduction?
I have to reduce $L_\text{empty}$ to $L_\text{inf}$
where
$\qquad L_\text{empty} = \{e \mid |L(P_e)| = 0 \}$ and
$\qquad L_\text{inf}= \{e \mid |L(P_e)| = \infty \}$.
where $P_e$ is the program ...
1
vote
1answer
67 views
A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language
Programmers do sometimes write a program that creates infinite loop if some particular input is passed into the program.
But Simply-typed lambda calculus has to stop - so the question is, can anyone ...
7
votes
2answers
117 views
Decidable languages and unrestricted grammars?
Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are.
We can define the decidable languages with ...
1
vote
1answer
31 views
computability - decidability of a prefix language
For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$.
If $L$ is decidable, is $L'$ decidable?
I think that $L'$ should be ...
3
votes
0answers
30 views
Polynomial Hierarchy and its Relation to Multi-Phase/States Physical Systems
We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to ...
1
vote
1answer
74 views
What is the difference between these terms?
Between my textbook and various online sources (namely wikipedia), I'm very confused... can somebody clear up which words are synonymous and which mean different things?
Many-to-one reduction
...
4
votes
2answers
101 views
Are co-semidecidable languages separated by decidable ones?
Can I use principles of set theory in order to solve the following question?
For every $A,B \in \mathsf{co\text{-}RE}$ with $A \cap B = \emptyset$, there is a separating language $C$ with $A ...
7
votes
2answers
123 views
A variant of the busy beaver function
Reading this question "Natural RE undecidable problems but not Turing-complete" the following language came to my mind:
If $\Sigma(\cdot)$ is the busy beaver function (maximum attainable score among ...
4
votes
1answer
80 views
Natural RE undecidable problems but not Turing-complete
The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not ...
2
votes
0answers
57 views
Non Turing-Recognizable from symmetric difference
I have a question about how you would find a example of a non Turing-recognizable language from the symmetric difference of two Turing-recognizable languages. I believe this is possible, but I am ...
2
votes
1answer
96 views
Is the ambiguity of a regular tree grammar decidable?
Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.g. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost ...
6
votes
3answers
126 views
Meaning of the Halting problem
The Halting Problem is defined as:
$H_{TM} = \{ \langle M, w \rangle \mid \text{\(M\) halts on input \(w\)}\}$
I'm not sure what it means. Is $H_{TM}$ a collection of Turing Machines such that all ...
