# Questions tagged [computability]

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

1,915 questions
Filter by
Sorted by
Tagged with
40 views

• 456
42 views

### Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$

I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. ...
• 456
26 views

### Prove that a Turing machine that looks to adjacent cells on left and right of a cell for decision is not weaker than normal Turing machine

We consider a Turing Machine that for a transition to apply, looks not only to the cell the head is currently on, but to its adjacent cells as well. Basically it will need to read a string of 3 ...
1 vote
53 views

### Enumerating through Turing Machines That Solve Same Problem

Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT ...
281 views

### Sets of problems in different models of computation and cardinality

In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg Essentially, Pushdown Automata (PDA) can solve ...
• 11
1 vote
34 views

### Are all Scott-continuous functions computable?

A chain-complete partial order (equivalently, a pointed dcpo) is a set $D$ with a partial order $\leq$ such that all chains of $D$ have a supremum. The least upper bound ($\bigsqcup$) of the empty ...
1 vote
24 views

### RP with very small error = P

I was asked to show the equality $RP(1 − 2^{-2^{n}}) = P$, which seems wrong to me (?). The $\supseteq$ direction is obvious, and I want to show the other direction. My first intuition was to run ...
• 161
31 views

• 181
1 vote
47 views

• 181
463 views

### How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is ...
• 181
27 views

### Prove that a predicate is not computable

Prove that the following predicate is not computable: $P_e(n) = \begin{cases} 1 & \textrm{if } \phi_n(n) = e \\ 0 & \textrm{otherwise} \end{cases}$ Could someone explain how to approach ...
1 vote
62 views

### Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable

Yet another question from an exe. in the Computability class taught by Z. Luria - I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable? I mean we ...
• 117
112 views

1 vote
37 views

### Does description method matter in Rice’s theorem?

If $\mathcal{p}$ is a nontrivial property of formal languages, then $L_{\mathcal{p}} = \{ \langle M \rangle \mid L(M) \in \mathcal{p} \}$ is undecidable by Rice’s theorem. What if we describe ...
50 views

### What is a computational problem?

I'm reading Sipser's "introduction to the theory of computation" book. Even though in many places the phrase "computational problem" appears there is no definition of it. How is it ...
• 101
41 views

### Language of Turing Machines that only accept their own encodings

Is the language $L = \{\langle M\rangle|L(M)=\{\langle M\rangle\}\}$ recursive? I've been trying for hours to find a way to prove or disprove that it is. My first attempt was to show it wasn't ...
36 views

### Counterexample that a program computes HALT(x, x)

Hello everyone I am having trouble solving this exercise question. I don't get it what do they mean by providing the value of input x ? It would be highly appreciated if anyone helps to clarify the ...
55 views

### How does one prove that DEC does not parameterize DEC?

The $n$th slice of a set $A \subseteq \Sigma^{*}$ is defined as: $$A_n = \{x \in \Sigma^{*}\mid\langle n,x\rangle \in A\}$$ The definition of parameterization is as follows - $C$ parameterizes $D$ (...
1 vote
54 views

### Confused about the concept of deciding in nondeterministic Turing machines

I read this discussion before. However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
78 views

### How to prove that regular languages are closed under reversal, inductively?

There are some threads that discuss it but I haven't came across an inductive one yet. All of them involve creating a finite automaton which I would like to avoid (as per my professors requests).
1 vote
42 views

• 11
116 views

### is HaltingFuck computable?

A while ago I defined the language HaltingFuck, but I've never been able to figure out its computational class. The language is defined as follows: HaltingFuck is a language very much like Brainfuck, ...
• 375
1 vote