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

0
votes
1answer
708 views

Is L={<M>|M is a TM and L(M) is uncountable} decidable?

Is $L=\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\}$ decidable? My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is ...
1
vote
2answers
50 views

Do NFAs with $\varepsilon$-moves never terminate?

Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser, Without reading any input, the machine splits into multiple copies one following each of the ...
1
vote
1answer
42 views

How can I build a fool proof security system? [closed]

From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not. That tasks looks very similar to me than deciding ...
2
votes
1answer
69 views

Halting problem for polynomial space bounded Turing machines

A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable. I do not ...
0
votes
1answer
50 views

Show that the following language is not recursive:

$L = \{w \mid M_w \text{exists and it accepts a word } x_1 = 0x \text{ if and only if it accepts } x_2 = 1x\}$ ($x \in \Sigma^*$, so $x_1$ is starting with a 0 and $x_2$ is obtained from $x_1$ by ...
1
vote
2answers
216 views

Reduce undecidable language to decidable language?

What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable): If $M$ accepts ...
0
votes
1answer
42 views

function application of N x N -> N

Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement. For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following ...
0
votes
2answers
39 views

computably defined function with non computable range

Are there examples of functions that can be defined computably, though the existence of their range is not computable?
1
vote
2answers
96 views

Is there a language that can be Turing-reduced from all languages?

I don't think so, because $A_{TM} = \{<M,w>\mid \text{M accepts w}\}$ is not Turing-decidable. Is this the right way to think about?
2
votes
1answer
121 views

Is the language of all deciders recognizing empty language decidable?

I TA for a course in theory of computation and this came up as an interesting question. $E_{TM}$ is the set of TM descriptions where the machine's language is empty. Of course, $E_{TM}$ is ...
1
vote
1answer
62 views

Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

Here is a quote from the Source 1: For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the ...
16
votes
8answers
7k views

Why can we assume an algorithm can be represented as a bit string?

I am starting read a book about Computational Complexity and Turing Machines. Here is quote: An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical ...
3
votes
0answers
42 views

Is there a name for the class of functions whose totality can be proved using “Ackermann-like” reasoning?

Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion ...
0
votes
2answers
68 views

Can any memory-less computer operation be represented in propositional logic?

Take any operation that is done by any type of computer (e.g. a cpu on a modern laptop), which doesn't use any type of temporary memory storage. I.e. this computer operation computes a function $f(x)=...
0
votes
0answers
78 views

how to prove that the diagonal language K is r.e

To prove that K= $\{x \mid \phi_x(x)$ halts and accepts$\}$ is r.e.: we can recognize K by: for any x, we simply run x on machine $\phi_x$ and accept if the machine accpets else reject and that's it.....
1
vote
1answer
38 views

A' not computable in A

Recall A'= $\{x \mid \phi^A_x(x)$ halts and accepts $\}$ In this article, a proof that A' not computable in A is given: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Flood.pdf He ...
1
vote
2answers
59 views

The set of valid sentences in FO is not decidable as a consequence of rec. inseparability

Two given languages $L_1$ and $L_2$ are called recursively separable iff there exists a recursive languge $R$ such that $L_1 \subseteq R$ and $L_2 \cap R = \emptyset$. Now consider first order logic, ...
17
votes
1answer
3k views

Can a computable function converge to an uncomputable number?

Does there exist a computable function $f:\mathbb{N}\rightarrow \mathbb{Q}$ such that: For all $t\in\mathbb{N}: 0\le f(t) < X$ $\lim\limits_{t\rightarrow\infty} f(t) = X$ Where $X$ is an ...
2
votes
0answers
95 views

Is there an analysis of the creation of axioms for a mathematical structure as a computational problem?

Historically, what has happened is the following: There is a "mechanical" structure, most importantly, arithmetic, which operates according to a set of well-defined rules that a stupid computer can ...
0
votes
1answer
87 views

How to solve this mapping reduction problem by proving the computability of this function?

I am working on a mapping reduction problem. Define the union of two languages $L_1,L_2\subseteq\{0,1\}^*$ to be $L_1 \cup L_2 = \{x0\mid x \in L_1\} \cup \{y1\mid y \in L_2\}$. I want to prove that $...
2
votes
0answers
39 views

Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
1
vote
2answers
156 views

prove A is co-re

Working on some cs theory and solving a problem on computationally [=recursively] enumerable languages: A language $A\subseteq \{0,1\}^*$ is co-c.e. if and only if there is a decidable language ...
1
vote
1answer
26 views

how to mapping reduce any r.e. language to the diagonal language K?

We know that the halting problem $A_{TM}$= $\{(e,x) \mid M_e(x)$ accepts$\}$ and the diagonal language K= $\{e \mid M_e(e)$ accepts$\}$ are mapping reducible to each other. Recall that A mapping ...
0
votes
1answer
68 views

how to mapping reduce any r.e. language to the diagonal language K?

We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation. I would like to ...
0
votes
0answers
79 views

show doubly connected graph is NL complete

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
1
vote
1answer
92 views

3-Col using each colour exactly $|V|/3$ times

Is the following problem in P? Does a graph $G$ have $3$-colouring, where each colour is used exactly $|V|/3$ times? I believe it is as we are trying to sample three sets (one for each colour) of ...
1
vote
0answers
28 views

Proving reducibility of a language to another language [duplicate]

I am self-studying formal languages and want to solve an example problem. Given formal languages $A,B\subset\Sigma^*$ over an alphabet $\Sigma=\{a,b,c\}$ with $$A=\{\omega\in\Sigma^*\vert\left|\...
1
vote
1answer
54 views

Reduce ATM to CFTM

How would I reduce $A_{TM}$ to $CF_{TM}$ when: $A_{TM}=\{<M,w>|M$ is a Turing Machine description and $w\in L(M)\} $ $CF_{TM} =\{<M> | M$ is a Turing Machine description $L(M)$ is a ...
2
votes
1answer
47 views

Adding the requirement of linear time on infinitely many inputs into the class $P$

Is the following problem computable in polynomial time? Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$) Output: $<M_2>$, encoding of a ...
0
votes
1answer
227 views

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages. The first part of the answer in a book said that: ...
0
votes
1answer
181 views

A second question on “Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs” [duplicate]

Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent ...
0
votes
1answer
1k views

Show that a language is decidable iff some enumerator enumerates the language in lexicographic order

The proof is given in the below: If $A$ is decidable, the enumerator operates by generating the strings in lexicographic order and testing each in turn for membership in $A$ using the decider. ...
6
votes
2answers
2k views

Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable. Does it make sense to discuss the complexity of computing a ...
2
votes
1answer
53 views

Question about proving that Rado's function is non-computable

I am currently following the proof, found here, that Rado's function $$ \Sigma (n) = \max \{ \text{# of 1's that may be written to a tape by an n-state turing machine} \} $$ is non-computable. Within ...
1
vote
1answer
102 views

How to prove these two distributions are statistically/computationally indistinguishable

First we generate a key, $$k \leftarrow \{\, 0,1 \,\}^{n}$$ And we construct two PPT algorithms $A$ and $B$ as follow: $$A_{k}\left( \cdot \right) \colon y_{A} \leftarrow k, \text{ return } y_{A}$$ ...
3
votes
1answer
221 views

is L = {<M> | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?

L is the language of all turing machines that its computing time on all inputs is O(n^2). my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make ...
3
votes
1answer
100 views

Understanding Applicative Evaluation Order with the Z-Combinator

I am trying to understand how the Z-combinator (Y-combinator for applicative order languages) definition came about. As Python is applicative I am using Python for this. So I know Python's evaluation ...
-3
votes
1answer
32 views

Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem

Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem. Well I did show that with reduction, by using $HP'$. Simply by creating a function from $f(\langle M \rangle, x) = (M')$ Thus,...
0
votes
0answers
591 views

Turing machine - Check if $a^p$ is prime

Question: Check if number of $a$ are prime with just two tapes in Tuning machine. I'm not quite sure how to check it but what I've got so far is: First tape will be the input. For example $aaaaa$ ...
0
votes
1answer
93 views

Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

PDA = Pushdown Automata Let's assume I have this language: $L = \{a^nb^ma^n | m,n \ge 1\}$ Would the first approach with one node be enough - in that case it guess twice the $\lambda$. In the ...
2
votes
2answers
263 views

Solve every problem with recursion [duplicate]

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks
5
votes
3answers
144 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
129 views

Reducing the infinite language problem to halting problem

Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $. It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$). How ...
2
votes
1answer
111 views

Proof: Kolmogorov complexity of string concatenation

Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$ where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means ...
1
vote
2answers
145 views

Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

Until just now I thought that I have fully understood Rice's theorem but this example irritates me: $L^* = \{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}...
1
vote
1answer
358 views

What is the difference between undecidable language and Turing Recognizable language?

I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask: Prove that the language $ A_{TM} = \{ \ <M,w> | \...
1
vote
1answer
54 views

prove every language got a language that is harder

I am prety stuck over here: prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$ $L''\ngeq L'$ basically it means L' is the hardest... my intuition tells ...
-1
votes
1answer
327 views
7
votes
2answers
783 views

Is the intersection of infinitely many recursive sets recursive?

Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable? I know the union need not be recursive, because deciding if ...
2
votes
2answers
47 views

Example of non extensible functions ( $f(x) \notin EXT $) for reduction

This is the definition of $EXT = \{x\ | \varphi_x\ can\ be\ extended\ to\ a\ total\ computable\ function \}$. I'm trying to proof that $\overline{K} \le_{rec} EXP$ and I can't think of an example of a ...