Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computability]

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

0
votes
1answer
18 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?
-1
votes
0answers
9 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
31 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 ...
1
vote
1answer
64 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 ...
2
votes
0answers
125 views
+100

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 ...
-1
votes
1answer
72 views

Can we find every 216 digit number combination? [on hold]

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 ...
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
43 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 ...
2
votes
1answer
78 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 ...
1
vote
1answer
19 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^*$ ...
1
vote
1answer
32 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
38 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
42 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 ...
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 ...
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))=\...
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) ?
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 ...
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
2answers
59 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 &...
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
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 ...
1
vote
1answer
37 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
33 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 ...
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 ...
0
votes
1answer
65 views

Computability - The language of all strings of even length

Define a language $L$ as follows: $$L = \{\langle M \rangle \in \{0, 1\}^* | M\text{ is a TM that halts on all strings of even length} \}$$ I can prove that $L$ is not decidable/recursive, but is it ...
-1
votes
1answer
53 views

Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?

The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...
1
vote
1answer
40 views

Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this ...
28
votes
4answers
4k views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

I encountered below statement by Alan M. Turing here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...
1
vote
1answer
55 views

Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable

Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps. My Thoughts: I am new to proving results like ...
2
votes
1answer
36 views

Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$

I've been stuck on this problem for a while. Any hints would be appreciated! Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
2
votes
1answer
54 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 ...
0
votes
1answer
42 views

Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$

I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one. Definitions: $$\begin{align*} CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a ...
1
vote
2answers
269 views

Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?

I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class: \begin{align} C=\left\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are ...
0
votes
1answer
19 views

Does $E_{TM}$ accpets the empty word $\varepsilon$?

Let $L = E_{TM} = \left\{ \left<M \right> | M \text{ is a TM and L(M)} = \emptyset \right\}$. Does $L$ accepts the empty word $\varepsilon$? In other words, is $$\varepsilon \in L$$ I'm ...
0
votes
0answers
26 views

Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?

i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book). on page ...
1
vote
1answer
29 views

Language decidable or not?

I have just began with my course of complexity and computability and I need your experience to help me progress !! Something is not clear for me: It is asked to determine if L1 is decidable or not, ...
2
votes
2answers
99 views

Can a TM recognize whether another TM recognizes a non-empty language?

Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$ Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm? My attempt: I wanted to study ...
0
votes
1answer
42 views

Enumerators and recognizers

I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ...
1
vote
2answers
62 views

Rice's Theorem - usage on $DFA$ or $LBA$

I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable. However I am not sure about one ...
2
votes
3answers
83 views

Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about. Given: $$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM ...
1
vote
1answer
70 views

is it possible to reduce $HALT_{TM}$ to $E_{TM}$?

I am wondering, if it is even possible: is it possible to reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$? $HALT_{\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }...
0
votes
0answers
68 views

Proving language K is undecidable using the diagonalization method

I have a problem proving the following properties of given language K: $K = \{< M > | M\ accepts < M >\}$ I am trying to prove that language K is Turing-recognizable but undecidable ...
3
votes
2answers
79 views

One counter automaton as a function

We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word ...