Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,626
questions
1
vote
1answer
34 views
Why is this language Turing recognizable and not not-Turing recognizable
I read that the following language is r.e. but not not-Turing recognizable
$L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs
I am not sure why it is not not-Turing ...
-1
votes
0answers
18 views
With Σ = {a,b}, give a dfa for L= w1aw2 : |w1 |≥ 3, |w2 |≤ 5}
I racked my brain,I saw other people's solutions and it don't make sense. I think my biggest problem is I don't know when one string ends,like for example w1 is >=3 and it can have how many ever b'...
0
votes
0answers
22 views
Is there a logic-to-numeral mapping which preserves uniqueness (contrary to the Gödel coding)?
Given the two equivalent terms $A \vee B$ and $B \vee A$, Gödel numbering returns two various codes $2^{4}.3^{\overline{A}+1}.5^{\overline{B}+1}$ and $2^{4}.3^{\overline{B}+1}.5^{\overline{A}+1}$, ...
1
vote
1answer
674 views
Is it true that if L* is recursive, L is also recursive?
Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive?
I know that the opposite direction is true:
If $L$ is recursive, then $L^*$ is recursive.
But I don't know how ...
1
vote
1answer
21 views
Why there is no Turing Machine that accepts the Diagonal Language?
Given the diagonal language
$$L_d = \{ i : \sigma_i \notin L(M_i) \}$$
Where $M_i$ are all Turing Machines and $\sigma_i$ are all the words, if you put in in a Matrix like this:
$$\begin{array} {|c|c|...
0
votes
1answer
57 views
Confusion of halting problem
Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.
lets P be program that determine one of the ...
0
votes
1answer
48 views
Is there a total binary computable function that specifies Turing machines with nonempty domain?
I am working through Bridge's computablity book and I came across this problem that does not have an answer. I don't know how to precede, any help is much appreciated.
0
votes
0answers
15 views
Time complexity - Head stay transition - Turing Machine
I'm checking time complexity in a turing machine.
There is a transition that doesn't move the head, it justs stays (not right nor left movement) .
Should I count that state transition to calculate the ...
0
votes
1answer
45 views
Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion
We know that the number of permutations possible for $n$ unique items is $n!$.
We can uniquely label each permutation with a number from $0$ to $(n!-1)$.
Suppose if $n=4$, the possible permutations ...
1
vote
1answer
34 views
What is the theoretical result of flattening a list containing only itself?
Consider the following python code
X = [None]
X[0] = X
This has many fun properties such as
X[0] == X
and
...
1
vote
0answers
34 views
How to show that these two disjoint sets $A$ and $B$ exist
I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them...
In this case, a set $C$ is said to ...
1
vote
0answers
33 views
What is sideways recursion
A friend of mine is studying business analytics, currently on the topic for Microsoft DAX, but he is very new to the technological field. He mentioned yesterday, during a conversation, the term "...
0
votes
1answer
26 views
Computability of Kolmogorov Complexity of Turing-Incomplete language
I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows:
$A;B \text{ - ...
-1
votes
1answer
36 views
Does 2SAT contained in SAT?
Is it true that $2 S A T \subseteq S A T ?$ and in general is $k S A T \subseteq S A T $ where k is any positive integer is true?
Thanks.
1
vote
0answers
37 views
difference between two uncomputable functions
for $L1$ regular language, $L2$ some language, $L1$ \ $L2$ is regular, decidable. yet, the next transition function might not even be computable:
$F′=${$\,q:δ(q,w)∈F \, for\, some\, w∈ L2\,$}$.$
$F$ ...
1
vote
1answer
25 views
Why Right-Division of regular language with RE\E language is regualr?
I think I can't understand the meaning of language being decidable.
The next case makes no sense to me:
Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
0
votes
1answer
29 views
Turing machine that can remember
Special Turing Machine is defined just like standard Turing Machine, only that each step is made according to the content of the tape starting from the left edge to the head position in tape.
(The ...
0
votes
1answer
29 views
Proving undecidability for a language which contains string with certain syntax
Lets say we have the following problem:
$$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three ...
1
vote
1answer
26 views
Is it correct to say L is RE if I can map reduction from LH to L?
I seem to be not understanding correctly what reductions means for Languages.
for example, Lets say there is a Language called LM.
I want to see if LM is recursive or not, to do that lets say I find ...
3
votes
3answers
517 views
Given A to C, and B to C with known complexities, what can be said about A to B?
Say I have two sets of values $A$ and $B$ and for each set I have a computable function from that set to a third set $C$. Now suppose that I want to construct a function from $A$ to $B$, such that if ...
1
vote
1answer
27 views
Prove a language is not recursive enumerable
I need to prove
$: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$
at first observation it looks like it's immediate from Rice's extended Thm, ...
0
votes
0answers
18 views
how to prove that $NP \cap co - NP$ = { S | S such that there exist a Strong Deciding Algorithm for S}?
i need to prove that and i find it struggle:
given:
for deciding problem S:
a non deterministic algorithm $A(x)$ is strong deciding algorithm if:
$x \in S =>$ fo every run of $A(x)$ returns "Yes"...
0
votes
0answers
31 views
Single-valued enumeration of all c.e. sets
Please help prove the following statement:
There exists a single-valued computable enumeration of the family of computably enumerable sets.
Definitions:
1) Let $S$ be nonempty countable set (...
2
votes
1answer
31 views
How to understand definition of $\Pi_k$ in arithmetical heirarchy
Am reading a text about computability theory, and according to the text, at each level $k$ of the arithmetical hierarchy, we have two sets, $\Sigma_k$ and $\Pi_k$, where $\Pi_k$ is defined as:
$$
\...
3
votes
1answer
59 views
Finding the upper bound of states in Minimal Deterministic Finite Automata
I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite ...
3
votes
2answers
143 views
Solving Exact2IS using IS
i encountered the following problem:
Exact2IS ={G has exactly 2 independent sets}
Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets.
(i ...
1
vote
2answers
39 views
Master Theorem applicable here?
Let
$T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\
1 & \text{if }n=1
\end{cases}$
I need to prove that $t(n) \in ...
2
votes
1answer
26 views
Decide if a language has a word of a given size
Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable:
$$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ ...
2
votes
2answers
281 views
What does the phrase “Simple For Loops” mean in computability theory?
I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me?
The Phrase:
...
0
votes
2answers
111 views
Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$
Given the language:
$MIN_{TM}$= $\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \}$
I need to prove if this language is in $R$ or $RE-R$ or $...
1
vote
1answer
31 views
Proving a certain primitive recursive function exists
Assume $f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $g\colon ω × ω → ω$ where the following holds:
$∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)...
3
votes
0answers
22 views
Random variate generation in Type-2 computability
Is there any existing literature on applying the theory of Type-2 computability to the generation of random variates? By "random variate generator" I mean a computable function $f\colon\subseteq\{0,1\}...
1
vote
1answer
213 views
Decidability of Turing machines that never move their heads past any input string
$L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$
$L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} ...
3
votes
1answer
45 views
Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials
Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form ...
2
votes
2answers
44 views
Domain of a Type-2 Computable Function
In Weihrauch's Type-2 computability theory, a string function $f\colon\subseteq \Sigma^{\omega}\rightarrow \Sigma^{\omega}$ (the $\colon\subseteq$ indicates that $f$ may be a partial function) is ...
1
vote
0answers
31 views
Kolmogorov complexity of a product of two numbers
In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal ...
0
votes
2answers
35 views
proving $E_{TM}$ is undecidable using the halting language
How to prove that:
$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$
(is undecidable)
using the language:
$H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$.
I tried to prove by ...
0
votes
1answer
43 views
If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$
If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ ?
Also I find it hard to find languages that are not in RE at all, I've heard about Arithmetical hierarchy but we didn't really learnt it in ...
1
vote
1answer
12 views
All total functions form a PRC class
A class of total functions is a PRC class if:
The class includes all projection functions $p_i(x_1,\ldots,x_n) = x_i$ and the initial functions $n(x) = 0$ and $s(x) = x+1$.
The class is ...
1
vote
1answer
105 views
Indexed family of all unary partial computable functions
Please help prove the following statement:
The indexed family of all unary partial computable functions that have total computable extension is computable.
Definitions:
Total function - a ...
0
votes
1answer
23 views
ODEs and Zeno Machines
Disclaimer: I know nothing about differential equations, and I don't know if this belongs here...
Wikipedia states that a Zeno machine is a hypothetical machine able to compute infinite
steps in ...
-1
votes
2answers
69 views
Halting problem - What if the halting algorithm gave more than one output?
Sorry I don't know how silly a question this might be, but i've been reading up on the halting problem lately, and understand the halting problem cannot possibly output a value that is "correct" when ...
20
votes
5answers
2k views
Halting problem theory vs. practice
It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.
But that only applies to an arbitrary program.
Has there been any study regarding classes of programs ...
0
votes
1answer
36 views
About computable sets
Let TOT be the set of all Turing Machines that halt
on all inputs.
Find a computable set B of ordered triples such that:
TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B]
This definition means ...
1
vote
1answer
80 views
Are these problems NP-Complete?
I got 2 decision problem that I need to answer if they are in P or they are NP complete:
1.Just like subset sum:
given the integers or natural numbers ${\displaystyle w_{1},\ldots ,w_{n}}$ does ...
1
vote
1answer
23 views
Is there a way to hash a turing machine?
If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
0
votes
2answers
45 views
How could you “solve” the halting problem if, hypothetically, the busy beaver numbers were “small”?
I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.
I'm trying to figure out how you could ...
1
vote
0answers
33 views
Decidability of equality of expressions involving exponentiation
Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special ...
1
vote
0answers
33 views
Turing-completeness of affine programs
Are unguarded affine programs Turing-Complete?
Are affine programs with affine guards Turing-Complete?
Unguarded program: all branches are taken
Affine program: only assignments like $x:=x_1+5x_2-...
1
vote
1answer
61 views
Is there a language that cannot be polynomially reduced to?
Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
