Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
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?

1
2 3 4 5
33