Questions tagged [computability]

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

0
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
2answers
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 ...
5
votes
4answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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$ ...
2
votes
1answer
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 ...
2
votes
1answer
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$ ...
-3
votes
1answer
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 ...
1
vote
3answers
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, ...
0
votes
1answer
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?
0
votes
1answer
13 views

Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?

My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\...
19
votes
5answers
850 views

What exactly is computation?

I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of ...
3
votes
1answer
36 views

Uncomputably coded model of computation

There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there ...
4
votes
3answers
288 views

Metagame Paradox: what is wrong with this explanation?

Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post ...
-1
votes
1answer
73 views

Can we find every 216 digit number combination? [closed]

This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?" So I want to find every possible 216 digit number ...
1
vote
1answer
65 views

Is “Query Equivalence” decidable?

I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall d ...
5
votes
3answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
12 views

Proving a language comprised of 2 languages is regular(with suffix and prefix)

I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular: $$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
0
votes
1answer
44 views

Advantages of Lambda calculus over Turing machine and vice versa [closed]

What kind of advantages does Lambda calculus have over Turing machine, and vice versa?
4
votes
1answer
17 views

Proving a language comprised of 2 languages is regular

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it. The question: $L_1$ and $L_2$ are regular languages over the ...
1
vote
1answer
20 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
2
votes
2answers
60 views

Is finding a single digit of a computation is as hard as finding the computation?

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages: $$\begin{align*} L_1 &...
6
votes
2answers
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 ...
1
vote
1answer
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), ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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. ...
3
votes
1answer
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 ...
1
vote
1answer
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: ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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) ?
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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:...
1
vote
0answers
22 views

Getting string from phrase structure grammar

For the following phrase structure grammar I want to construct the type of string that satisfy it, but I am not sure the way to go. $$\begin{align*} S &\to xTy \\ T &\to xTT \\ xTx &\to ...
1
vote
1answer
38 views

How precise to be when describing a Turing machine?

I'm kind of new to the theory of computation and I was working on this problem: We say that a Turing machine $M$ uses $k$ squares of tape for an input string $w$ if and only if there exists a ...
1
vote
0answers
26 views

Theory for programs that are “embedded” in other programs?

We can make the following distinctions: (I will use the term "program" and "machine" as synonyms). A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes ...
0
votes
1answer
34 views

NP-Complete is not closed under kleene star

Consider $\Sigma=\{0,1\}$. Suppose that $L \subset \Sigma^*$ is $NP-$Complete. How can I prove that $L' = L \cup \{0,1\}$ is $NP-$Complete?
2
votes
2answers
56 views

Pumping lemma occurrence of c > d

I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it. The alphabet is: $$ \Sigma = \{c, d\} $$ The language is: $$ A = \{z ...
3
votes
1answer
115 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?
1
vote
1answer
36 views

Give a computation of the expression to normal form (Lambda calculus)

Past exam question: What my understanding of B-reduction is : Find all occurrences of the parameter in the output, and replace them with the input and that is what it reduces to ...