Stack Exchange Network

Stack Exchange network consists of 174 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

1
vote
2answers
114 views

How to prove that if the set and its complement are recursively enumerable, then both are recursive?

How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive? My idea is that we can make the characteristic function of recursively ...
2
votes
1answer
73 views

Decidability of a set containing first symbols of elements of a decidable set

Let's say we have an alphabet $\Sigma = \{a,b, \dots , z\}$ Set $A$ consists of words $x_i$ containing symbols from $\Sigma$ alphabet, which have this structure $x_i := \alpha_i \beta_i$, where $\...
3
votes
1answer
294 views

How is deciding a problem not equivalent to finding a valid certificate for verification?

Take a decision problem $Q$, which maps encoded instances of a problem, i.e., $\lbrace 0, 1 \rbrace \ast$ to the solution set $\lbrace 0, 1 \rbrace$. Since $Q$ is in $NP$, there exists a verification ...
0
votes
1answer
53 views

Turing machines and their computational power

Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the ...
0
votes
1answer
70 views

Are there any implementations of computability logic?

I'm currently looking into Japridze's computability logic. It looks great, but I was wondering whether any programming languages or systems implement it. Does anyone know of any implementation? ...
6
votes
2answers
1k views

Why does the copycat strategy work for two parallel chess games?

I'm currently looking into computability logic. Japaridze explain that a game !P v P like !Chess v Chess is always winnable thanks to the copycat strategy (http://www.csc.villanova.edu/~japaridz/CL/3....
2
votes
1answer
127 views

Decidability of L

I have the following problem. If L is decidable and L = L1 u L2 (union). So are L1 and L2 decidable, too? I know that, if L is decidable, the complement is also. And this means the complement is ...
3
votes
1answer
49 views

Connecting strings in a graph is a PSPACE problem

We define the following problem as: Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$. We define, for every natural number $n$ the graph $G_{M,n}$ by: $V_{M,n} = \{a,b\}^n$,...
0
votes
1answer
46 views

Obtaining a computational history of a Turing Machine

I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In ...
2
votes
1answer
69 views

What is the current state of the art in solving the halting problem? [closed]

Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them. To be a little more ...
1
vote
1answer
44 views

Give a Search Problem in co-NP

Ex.1. Give a Search Problem whose deciding Problem is in co-NP. Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right? Then would asking ...
0
votes
0answers
21 views

Karp Reduction L1 ≤p L2

Given: $L_1 = \{0^k1^k|k \in \mathbb{N}\}$ $L_2= \{1\}$ $L_1 \leq_p L_2$ There must be a function $$f:Σ^* \rightarrow Σ^*$$ such that $$w \in L_1 \iff f(w) ∈ L_2$$ Let's say a word in $L_1$ is ...
1
vote
1answer
101 views

Turing Reduction vs Karp Reduction [closed]

When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages? I've read about Karp Reduction mainly used in the Context of reducing a Language: e.g. L1 $≤_p$ L2
1
vote
1answer
114 views

A question about proving Rice's Theorem by reducing it to the Halting Problem

I've read the definition for Rice's Theorem, here's the one from Wikipedia: In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. ...
1
vote
1answer
109 views

Decidability of determining whether a context-free grammar generates all strings in 1*

How could I prove that the following language is decidable? $\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$ P.S. It's the problem 4.15 of the third ...
0
votes
1answer
35 views

Why we write “Ignore the input ” when describing an Enumerator?(Sipser Chapter 3)

The Theorem and its proof is given below: But I am wondering why we write "Ignore the input " when describing an Enumerator? could anyone explain this for me please?
-1
votes
1answer
33 views

mapping reduction from $A_i=\{x|i \in W_x\}$ to $A_j=\{x|j \in W_x\}$

If $$ A_n = \{ x | n \in W_x\} \ where \ W_x \ is \ domain \ of \ M_x $$ how can I show that $$ \forall i,j \ \ \ A_i \le_M A_j $$
2
votes
1answer
52 views

Determining whether the language of a DFA is closed under reversal

The question and its answer is given below: Let $S = \{ \langle M \rangle \mid \text{$M$ is a $\textsf{DFA}$ that accepts $w^{\mathcal{R}}$ whenever it accepts $w$}\}$. Show that $S$ is decidable. ...
2
votes
0answers
99 views

Simulating a turing machine with DPDA with two stacks

In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. ...
0
votes
1answer
90 views

Proving that DFA equivalence is decidable

The following question is taken from Sipser: Prove that $EQ_{\mathsf{DFA}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works. Here is the ...
1
vote
1answer
21 views

What is the output of a 2-tag system?

Considering a 2-tag system as defined by wikipedia, how do I identify the result of the computation?
-1
votes
1answer
44 views

Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$

Given $A, B$ languages over $\Sigma,$ Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$. I would like to disprove this claim, with the languages $H_{TM}$ and $H_\epsilon = \{\langle ...
0
votes
1answer
47 views

is it possible to have a mapping reduction between 2 NP complete languages?

so i have a good understanding about languages that belong to NP, P and NP complete, and how Polynomial reduction works between languages that belong to those areas. but i just can't figure out a ...
0
votes
0answers
24 views

Prove that a language is undecidable by reducing HALT to it [duplicate]

Let $L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$ and $HALT = \left\{ \langle \alpha, x\rangle \mathrel{}...
0
votes
0answers
29 views

Calculus methods and computability

We know about calculability of a function or computability. We looks for the ability to solve a specific problem / compute a function with calculus method. But if we define a calculus method, is ...
4
votes
1answer
566 views

Do “Type-2” Turing machines with infinite length inputs have more computational power?

Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of ...
4
votes
0answers
46 views

The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
2
votes
1answer
38 views

When does an extendible 1:1 p.c. function have a 1:1 computable extension?

A partial computable function $\varphi_e$, defined on a c.e. set $W_e$, is called extendible if there exists some computable function $f$ which extends $\varphi_e$, i.e. $\varphi_e(W_e) = f(W_e)$. My ...
2
votes
1answer
76 views

Language of all words accepted by a TM by at most $t$ steps is regular

Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$ $L = \{ w \in \Sigma^* : w$ is accepted by $M$ by at most $t$ steps$\}$ I want to show that $L$ is regular. My attempt: I'm ...
3
votes
2answers
61 views

Alan Perlis Epigram on Recursion

So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis: Recursion is the root of computation since it trades description for time. -- ...
2
votes
1answer
54 views

If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable? I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example. Can ...
2
votes
0answers
30 views

Nearest codeword in a translation-invariant code over $\mathbb{Z}^d$

Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support. Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$. It is possible to calculate the nearest codeword $...
0
votes
1answer
119 views

Are the implications of the diagonalization language different from those of the halting problem? [duplicate]

Revised: In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing ...
2
votes
1answer
66 views

Transitivity of quasi-reducibility

A set $A$ is quasi-reducible to $B$ ($A \leq_Q B$) if there is a recursive function $f$ such that $$x \in A \iff W_{f(x)} \subseteq B$$ Or equivalently $$ x \in \overline{A} \iff W_{f(x)} \cap \...
2
votes
1answer
86 views

Are there connections between the theory of computation and machine learning?

I am wondering if studying the Theory of Computation/ Computational Complexity theory, specifically Sipser's 'Introduction to the Theory of Computation' will help me do machine learning/statistics/...
0
votes
0answers
20 views

How do I solve this function using basic instructions?

The function $f$ takes two integers and produces one integer $f(a,b) \vdash 3*(b-a)$ The only instructions I can use are +1, -1...
3
votes
1answer
90 views

Any common problems solvable by DFA/NFA or PDA except recognizing languages?

I understand that DFAs recognize regular languages, and PDAs context-free languages, but these are a little bit too theoretical. I am wondering if we can implement common functions or solve common ...
1
vote
1answer
62 views

Proving that for every computable function f: N → N, there exists a computable function g: N → N such that for every n we have f(n) ≤ g(n)

Prove that for every computable function $f \colon \mathbb N \to \mathbb N$, there exists a computable function $g \colon \mathbb N \to \mathbb N$ such that for every $n$ we have $f(n) ≤ g(n)$. Can ...
0
votes
1answer
48 views

Language Decidability

What is the easiest and the most straightforward way to find whether a given language is decidable? For example, how do we know if the following languages are decidable or not? ...
0
votes
1answer
170 views

Why is the intersection of these two Languages Recursively Enumerable, not Recursive?

I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language ...
2
votes
1answer
24 views

Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P

The question and its answer is given in the following picture: But I do not understand why stage 2 causes at most $n+1$ repetitions, and why stage 3 uses at most $O(n^2)$ steps, and I understand that ...
3
votes
1answer
84 views

Is Blum's theorem for acceptable enumerations of partially computable functions bidirectional?

Theorem II.5.8 in P. Odifreddi's Classical Recursion Theory states that If $\{\psi_e\}_{e\in\omega}$ is an acceptable system of indices, then there is a recursive permutation $h$ such that $$ h(\...
1
vote
1answer
35 views

Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

Sipser provided the following proof to prove the mapping reduction from $A_{TM}$ to $HALT_{TM}$, it in fact tried to build a mapping function: My problem is the way this proof works. The function ...
4
votes
2answers
2k views

Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
0
votes
0answers
35 views

Forever running programm computable?

Is a forever running program computable? For example a program which calculates the biggest natural number.
1
vote
1answer
35 views

Why is this function computable

I'm struggling to understand why this function is computable. This is the requirement: Consider the following program P, written in a pseudo-C language: ...
0
votes
0answers
82 views

Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
0
votes
1answer
46 views

Problem with proving the undecidability of REGULAR$_{TM}$

Sipser in his book provided the following proof for undecidability of REGULAR$_{TM}$: S = “On input $<M,w>$, where $M$ is a TM and w is a string: Construct the following TM $M_2$. ...
-1
votes
1answer
52 views

Is the language of TMs running in polytime Turing-recognizable?

Any ideas for proving that $L=\{\langle T \rangle : \text{ time complexity of $T$ is polynomial}\}$ is not Turing-recognizable?
1
vote
0answers
35 views

product of fully time constructible functions is fully time constructible

How would you prove that product of two fully time constructible functions is fully time constructible? I managed to prove for sum, but product seems more complicated