# Questions tagged [computability]

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

1,829 questions
Filter by
Sorted by
Tagged with
27 views

### Difference between Counter-machine and stack machine

I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). My question is counter machine means counter coexist ...
11 views

### Need literature on First order logic definibility through Automata

Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
39 views

44 views

### $\Sigma_3$-completeness of REG

Show the the following language is $\Sigma_3$-complete: $$\mathrm{REG} = \{ \langle M \rangle \mid L(M) \text{ is regular}\}.$$ Using the quantifier method I figured out that REG is in $\Sigma_3$, ...
13 views

### The Turing Machine in the proof of Time Hierarchy Theorem

In the proof of the Time Hierarchy Theorem, Arora and Barak writes: Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
34 views

### Reasoning given with explanation of Halting Problem

I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the ...
55 views

### Checking whether given measures qualify as computational resources

Do the following measures qualify as computational resources? number of even-numbered states that the machine $M$ visits on input $x$ number of times that the machine $M$, when run on input $x$, ...
45 views

### Reduction of $RE$ language

Suppose that the language $L_1$ reduces to the language $L_2$ in polynomial time, $L_1\leq_p L_2$. If $L_2$ is recursive enumerable then so is $L_1$, but why isn't $L_1$ recursive? Because $L_2$ is at ...
17 views

### Can an instance of the post correspondence problem have exactly one solution?

Can an instance of the Post Correspondence Problem (PCP) have exactly one solution?
19 views

### Would a computable universe imply computable physical constants?

Suppose it does turn out that the universe consists entire of deterministic computation, that it could be running on a Turing machine in principle. Physicists in particular don't seem to think that's ...
45 views

### Reduction from recursive language to recursive enumerable

If any language $L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
65 views

### Rogers (Kleene)'s fixed-point theorem and the Y combinator

In the Wikipedia article on Rogers' theorem, it is stated that the proof given by Rogers is a construction of a partial recursive function which implements the Y combinator. I've just a basic ...
23 views

### Can we combine two non-terminals and use this as one non-terminal in CFG?

Let's consider this CFG- S->AB [Here, **S** is the starting variable] A->C CB->Cb C->a Now, the question is- Check if ab is a valid string for the ...
60 views

### What is the the greatest thing a computer has trouble doing?

If we have all these optimized programs for very specific tasks, what would be the antithesis of them? I've asked a programmer friend of mine, and they thought a good answer had to do with multi-...
15 views

### How is it possible that for infinite L in R exists subset L' which is not in Re?

Proove that for every infinite $L \in R$ there is a $L' \subseteq L$ s.t $L' \notin RE$. How can I proove it? if sketched on venn diagram it doesn't make sense... From my point of view everything ...
39 views

### How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this. Is this true? Thanks, friends :)
29 views

### What does it mean for an integer to belong to the halting problem?

I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this ...
45 views

### Does $L_1L_2 \notin RE$ imply $L_2L_1 \notin RE$?

Given two languages $L_1, L_2$ such that $L_1L_2\notin RE$, is it always true that $L_2L_1 \notin RE$? I wasn't able to prove it or find a valid counterexample.
217 views

### Must a partial halt decider be a pure function of its inputs?

Must a partial halt decider be a pure function of its inputs? A partial halt decider correctly decides the halt status of some of its inputs. I am trying to write C code that would be acceptable to ...
101 views

### What is the regular expression for the language, {w | w does not contain the substring 11}

{w | w does not contain the substring 11} What I am thinking: $(0^* 1 0^* )^*$ Is anything wrong with my expression? Thanks in advance for your help!
47 views

### What is the sequence that is computed by a Turing machine?

so I was wondering how to know the sequence a Turing machine T computes? We are reading The Annotated Turing by Charles Petzold at the moment which includes Turing's original paper "On Computable ...
53 views

### Turing machines which halt after updating a cell for the second or third time

We say that a Turing machine is fragile, if it halts after changing the symbol of one of the tape cells for the third time. Is it true that every language that is solvable on a Turing machine will be ...
31 views

### Equivalence between $\lambda$-calculus and recursive functions

I have two related questions: Do you know of any good reference to the recursive function / lambda-calculus equivalence in terms of computability, including proofs? Do you know of any reference to ...
60 views

### Can you diagonalize a language out of CSL?

In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
23 views

### Recursive Bijections Between Countably Infinite Sets

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
36 views

### Language classification

I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R. The ...
43 views

### How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
28 views

### Computation branches on NTM

I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string. $\text{Start: }(q_0) 011101$ ...
28 views

### Is this language in RE?

Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE). I used Rice Theorem as follows to ...
39 views

### What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?

For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
85 views

### Necessity of encoding for certain models of computation

Consider the following model of computation (from here). Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
49 views

### If a computer can demonstrate singleton sets are closed, is the space Hausdorff?

In Haskell, I made a class of admissible (that is, second-countable and $T_0$) spaces: ...
54 views

### Given a string which was produced by mixing up a string of digits, find the original digits

I encountered the following problem: Given a string which was produced by mixing up a string of digits (0-9), for example: "otetwonhree" was produced by "onetwothree"~123, find ...
45 views

56 views

### Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
37 views

### Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
91 views

### Reduction from the SAT problem to the NAE-SAT problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
136 views

### edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...