# Questions tagged [computability]

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

2,052 questions
Filter by
Sorted by
Tagged with
46 views

### Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
21 views

### L in NP and L is coNP-hard=>NP = coNP

How can I prove this: given this 2 sentences 1 <=> 2: There exists a language L ∈ NP that is coNP-hard. NP=coNP. the direction from 2 to 1 I can prove using the concept of NP-cpmplete and etc. ...
36 views

### Polynomical reduction from language to NP language

Given a language $L$, if I can deduce that $L \le_p L'$, where $L'$ is in NP, can I conclude that $L$ is in NP too?
27 views

### Proving that if semidecidable, then computable

Definition: The graph of an n-ary function F is the n+1-ary relation $G_F$ defined by $G_F(a_1,...,a_n,b) \Leftrightarrow F(a_1,...,a_n)=b$. Theorem: if $G_F$ is semidecidable, then $F$ is computable. ...
• 103
26 views

### Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

All I know about this language is that it is equivalent to the following: $$L = \{w \in \{a,b,c\}^{∗} : n_b(w) + n_c(w) = 2 * n_a(w)\}$$ but I have absolutely no idea how to create a CFG for it.
129 views

### Analog computers more powerful than turing machines?

Ignoring quantum mechanics for a moment, is it true that analog computers are more powerful than turing machines? for example an analog computer can add two irrational numbers together, but a turing ...
• 324
48 views

### Computability- relationship between R, coRE and RE

I am trying to think of a question that discusses the relationship between RE, coRE and R. Namely- is it true that for all For every language 𝐿1∉ RE there exists a language 𝐿2∉ coRE such that 𝐿1∪𝐿...
• 31
51 views

### Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

I've been researching formal models for computing with real numbers and came across the field of computable analysis built on top of specifically the type 2 Turing machine, which allows for ...
8k views

### Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

According to the Bekenstein bound, Turing machines are not realizable in real life. So why are they accepted as the standard for effective computation? You may as well consider more powerful machines ...
• 324
41 views

### Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

The membership problem $A_{LBA}$ for a deterministic $LBA$ is decidable because the number of configurations that a $LBA$ can assume is finite. Since this number is also finite for a non-deterministic ...
• 139
38 views

### Why are languages fed as input into machines/automata as a stream and why do automata read one symbol at a time?

Consider an FSM augmented with a camera. The input is a book. First, the book is already stored without the FSM needing to have states to memorize the input. (The memory used to record the input is no ...
• 324
1 vote
30 views

### Computable function $F$ such that $F(e, x) = f(x), \forall x \in \mathbb N_0$

Is there a computable function $F: \mathbb N_0^2 \rightarrow \mathbb N_0$, such that for every computable function $f: \mathbb N_0 \rightarrow \mathbb N_0$, there exists an $e \in \mathbb N_0$, such ...
• 113
22 views

### Are there any example of practical application of counter machines?

I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
1 vote
66 views

### Gödel's theorem and machines' power

I was studying AI and when a question came to my mind. I know that one of the objections to the possibility of a thinking machine examined by Turing is the so called mathematical objection, ...
21 views

### Issues in the proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$

I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed). Consider this extract: M1 = “...
101 views

### Can remainder mod 2 be efficiently computed from addition and equality?

Suppose I have a programming language all of whose variables have natural number type. (So I cannot form higher-type objects, e.g., lists or trees, of natural numbers.) The only atomic commands I am ...
• 131
608 views

### Can the minimisation operation be seen from a programming language perspective?

If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion ...
• 133
329 views

### Is every non-recursively-enumerable language RE-hard?

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard? It seems like a simple question but I can't find an answer. I tried to ...
• 151
57 views

### Why is $RP \subseteq BPP$?

Lets define $P_M(x)$ as the probability that machine M accepts x. Let $L \in RP$. Then, if $x \notin L$, we get that $P_M(x)=0$, which is less than $\frac{1}{3}$, so all good here. But if $x \in L$, ...
• 191
79 views

### Is there a well-defined bijection between an undecidable language and the set of natural numbers?

The common belief is that every formal language is countable, based on the claim that "every subset of the natural numbers is countable." In the article https://homepage.divms.uiowa.edu/~...
72 views

### Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?

There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. ...
• 359
788 views

### Are there infinite state machines, and how do their computational power relate to turing machines?

From the internet: ...
• 324
71 views

### What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be ...
2k views

### If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

I have only begun studying this subject and have only completed the first few chapters of the Elements of the Theory of Computation. I have seen the answers (on this site and elsewhere) saying that ...
1 vote
137 views

### Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
• 13
83 views

### What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
• 13
107 views

### Decidability of whether a Turing machine accepts all even-length words

In my quest to understand computability theory, I came across this question, and it made me think that I don't fully understand the theory. Is this language decidable? Is it semi-decidable, co-semi-...
• 203
1 vote
59 views

### Is $L = \{ \langle G,k\rangle \mid G$ has a simple cycle at length $k \}$ in P or in NP

$L = \{ <G,k> |\ G \ has \ a \ simple \ cycle \ at \ length \ k \}$ I think this language is in NP but my friend thinks this language is in P. NP proof: if a graph has a simple cycle of a ...
• 203
125 views

### Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
55 views

### Are there some additions that a Turing machine cannot perform

The total number of Turing machines is the cardinality of the set of natural numbers. Now consider the following functions f1(x) = x + 1 f2(x) = x + 2 f3(x) = x + 3 and so on Since the total number ...
90 views

### PSPACE and Polynomial reduction

thanks for your help. This is my first question, so I am very sorry for the bad presentation of the question. I am studying computer science and this is the question I have been asked for the course ...
1 vote
52 views

### Is it known, whether the complement of NP-hard problems is necessarily again NP-hard?

Neither could I find any counterexamples, nor could I show that if indeed the complement of NP-hard problems was NP-hard, one could deduce some unknown results from it, which would imply that it is ...
1 vote
45 views

### Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...