Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
29 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
20 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
47 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
499 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\...
1
vote
1answer
30 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
61 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
188 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
493 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
44 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
43 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
40 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
39 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
42 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
57 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
47 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
0answers
40 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
53 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
49 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 ...
0
votes
0answers
30 views

Decidability for $ \exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

I tried to decide wheter the given Language $ L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \} $ is recursive or ...
0
votes
1answer
77 views

Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
0
votes
1answer
38 views

Are all Recursively Enumerable languages which are not Recursive also Undecidable?

Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable? R.E. ==&...
0
votes
1answer
32 views

What is minimization (μ-function) in layman tems?

In Computer Science μ-function is used to extend set of primitively recursive functions to generally recursive functions, and I can't understand what this function does. There is a lot of formulae, ...
0
votes
1answer
82 views

What's wrong with this “proof” that $\mathbb{R}$ is enumerable?

The fake proof: We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it. But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable. We ...
1
vote
1answer
43 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
1answer
50 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
698 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
51 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
64 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
56 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
17 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
60 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
36 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
36 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
45 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
30 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
37 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
38 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
32 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
32 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
30 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
35 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
520 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
33 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
67 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 ...

1
2 3 4 5
33