# Questions tagged [computability]

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

1,452 questions
9 views

### Herbrand structure of satisfiable clauses

Hello I am torn with the following clauses to either prove satisfiability or non satisfiability. I am looking for the Herbrand structure of these clauses (if there are satisfiable). (Satisfiability ...
38 views

### Is halts-if-valid decideable?

I have a suspicion that Turing's famous proof that the halting problem is undecidable may not prove exactly what people assume that it proves. It may only prove that it is possible to limit the ...
227 views

### How does a Turing machine with one tape read its input?

It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that ...
36 views

### Is function number of TM which terminates on an empty word computable?

Let f: N → N be a function where ...
29 views

### Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?

Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and ...
2k views

### Are Finite Automata Turing Complete?

Something is Turing Complete if it can be used to simulate any Turing Machine. So, can a Finite Automaton simulate a Turing Machine? On the question Can regular languages be Turing complete? they ...
40 views

### Longest simple circuit and P=NP relation

Given the following function: $$\:f\left(G,v\right)\:=\:size\:of\:the\:longest\:simple\:circuit\:in\:a\:directed\:graph\:G\:that\:contains\:v$$ Output: Function returns a natural number or 0, which ...
17 views

### Cubic space reduction variation of PSPACE-COMPLETE(Theoretical, tricky)

i've been wondering: if we change the definition of a PSPACE-COMPLETE definition to the following: A language B will be called PSPACE-COMPLETE if: for each language A in PSPACE: $A \leq _{CS} B$ ...
60 views

### Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can I just use ...
157 views

### Mapping reducibility from recursive to recursively enumerable language

I want to find out whether, assuming a language $L_1$ being mapping reducible (i.e., $L_1$ maps to $L_2$ and the complement of $L_1$ maps to the complement of $L_2$) to a language $L_2$ and $L_2$ ...
49 views

### Church Turing thesis

What is the exact statement of the Church Turing thesis? Is it fair to say anything computable in the physical world can be computed by a Turing machine? If so, how does a Turing machine handle ...
6k views

### Turing machine that increments a binary number by 1

I was asked to construct a Turning Machine that computes the increment of a binary string by 1- The Turing Machine receives a binary string and accept a string which is an increment by 1 of the input, ...
19 views

### In a Turing machine, what is the difference between the instruction table and the algorithm?

In a Turing machine, what is the difference between the instruction table and the algorithm? The instruction table seems to be an algorithm for completing the task no?
13 views

207 views

### Defining computable functions on arbitrary sets

Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to ...
38 views

### Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
79 views

### Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
12 views

8k views

### How to prove that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable? I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts ...
33 views

### Examples for Partial Combinatory Algebras

I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), ...
39 views

### Intersection of a recognizable language and a decidable language is decidable?

I'm having trouble with proving that "Intersection of a recognizable language anda decidable language is decidable. I assume this is true although I have no idea how to proof it. Can somebody point ...
17 views

### Why does the unbounded $\mu$ operator preserve effective computability?

Let $f$ be a partial function from $\mathbb{N}^{p+1}$ to $\mathbb{N}$. The partial function $(x_1,...,x_p)\mapsto \mu y[f(x_1,...,x_p,y)=0]$ is defined in the following way: If there exists at least ...
49 views

### Number of Function Calls In Recursive Code

I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes. ...
53 views

### Is the language of all TMs *not* accepting a given string, Enumerable?

Is the following language in RE? $$L = \{\langle M\rangle : M\text{ is a TM that does not accept }010\}$$ I could use Rice's Theorem with the property $P = \{L : 010\text{ is not in }L\}$ to show ...
30 views

### Reduction from minimum dominating set to the set cover

To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem. For example to find the MDS of the graph G: We can create an instance of the Set Cover problem by: ...
43 views

### Lazy streams and infinite series

I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard: A ...
56 views

### Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length

Prove that the language $$L=\{\langle M \rangle \mid \exists M_1, M_2 : L(M_1)=L(M_2)=L(M) \text{ and } |\langle M_1 \rangle| < |\langle M \rangle| < |\langle M_2\rangle| \}$$ is not ...
191 views

### Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let $$L_1 = \{(\langle M\rangle, w) \mid \text{M is a TM that accepts w and doesn't accept \varepsilon}\}$$ where TM is ...
17 views

### Prooving equations are non derivable in Sigma algebra

Let Σ be the signature made up from the following symbols. e: 0 arguments function (constant symbol) f: 2 arguments function g: 1 argument function Variable set Var is made up from x,y,z Let E be ...
26 views

### Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
38 views

### Recognizing Regular Languages in Layman terms [duplicate]

I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular. I know that ...
1k views

### Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
57 views

### how can this function be computed in polynomial time in regards to its input?

i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length) defining a function from assignments ...
64 views

### Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
22 views

### Complexity of the language of all TMs $M$ such that $L(M)$ is decidable
Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?