Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
2,055
questions
0
votes
0
answers
77
views
Non-universal Turing Machines and NP-completness
Is it true that a given problem is strictly NP-complete iff it's only decidable by universal Turing Machines? Similarly, a problem is in P iff there exists a non-universal Turing machine which solves ...
- 1
2
votes
1
answer
364
views
Showing that a property is semantic - Rice's theorem
I want to show that the language
$$L= \left\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\
\text{if M halts on input $w$, $M'$ halts on $w$ ...
- 161
0
votes
0
answers
49
views
DJNZ command in Universal Register Machine
How do I represent DJNZ command of counting machine via commands of Universal Register Machine, those commands are CLR JNE INC and TR, via this commands i have to represent DJNZ command, any help ...
- 1
0
votes
0
answers
81
views
Prove a Predicate is Primitive Recursive
Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula.
Prove ...
0
votes
0
answers
24
views
Is it possible to design an algorithm to estimate the future state?
I wonder if we take the current state of our machine as input, is it possible to generate a function to estimate the future state?
Of course I mean like we get the 10 minutes after status within 1 ...
- 1
1
vote
1
answer
59
views
Is the given language regular, CFL or in P
someone sent me a question lately and I wasn't able to solve it so I'm asking for help.
Question: Given the language
$$L=\{w\in\{0,1\}^*:|w| \text{ is even and the first half of it has a balanced ...
- 449
0
votes
1
answer
52
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. ...
- 449
1
vote
1
answer
104
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 ...
- 11
0
votes
1
answer
316
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 ...
- 19
2
votes
1
answer
86
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 ...
- 145
1
vote
0
answers
26
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
2
votes
0
answers
37
views
Universal register machine that recognizes the image of a partial function
Suppose $f$ is a $\mathbb N$-valued partial function over a subset of $\mathbb N$. If $f$ is computable by a universal register machine program, is the constant partial function
$$
g:\text{image}(f)\...
- 21
2
votes
2
answers
101
views
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
Consider the following problem:
Input: A Turing Machine M and a DFA D.
Question: Is $L(D) \subseteq L(M)$?
Of course, this problem is not decidable. Because it is known that judging whether a word ...
- 23
1
vote
2
answers
1k
views
How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
We know that $L
= \{ xy | x, y \in (0 + 1)^*, |x| = |y|,
x≠y\}$
is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by ...
- 317
1
vote
1
answer
83
views
Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
- 345
3
votes
1
answer
119
views
What are some examples of non-enumerable languages whose complement isn't either?
What are some examples of non-enumerable languages whose complement isn't either? I.e., a language L such that L is not Turning-recognizable and L’ is not Turing-recognizable either.
Update: Found ...
- 201
0
votes
1
answer
58
views
DFA for the language of non-empty words that are no longer than $2^6$
I was given a question in Automata that I need to prove or disprove, and I thought about this language:
$$L = \{w\in \{0, 1\}^*\mid 1\le |w| \le 2^6\}$$
Can you please help me to figure out if its ...
- 3
1
vote
1
answer
129
views
Proving Undecidability of this Language
Consider the language
$$L = \{\langle M \rangle \mid \text{$\exists$ an input $x$, where $|x|<i$, such that $M$ halts on $x$, but it takes at least $j$ steps} \}$$ where $i$ and $j$ are fixed non-...
0
votes
1
answer
58
views
If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable
I should prove or give a counterexample to the above statement.
In my opinion, this statement is false but I don't manage to find the right counterexample.
My idea was to define $C = Σ^*$ because $Σ^*$...
- 217
1
vote
1
answer
310
views
How would I show function $f(x)=4x$ is Turing computable?
How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable?
My guess is obviously there is a finite number of operations ...
- 135
1
vote
2
answers
137
views
Reduce instances of a-Turing-machine-does-not-accept-a-string to Turing machines that accept the empty string
I am struggling with a mapping reduction that I think cannot be correct, but I'm not able to say exactly what's the problem.
Let $L_{u}= \{\langle M,w\rangle \mid M\text{ accept }w\}$, $\overline{L_{u}...
- 55
1
vote
1
answer
288
views
A decidable language that can't be decided by a circuit ensemble of linear size
Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
- 11
-2
votes
1
answer
241
views
Halting problem. Decider “recognising itself” in the input? Part 2
This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
- 1
0
votes
0
answers
160
views
Prove that the problem of REGEX producing strings with 111 as substring is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given <...
- 17
1
vote
1
answer
1k
views
Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable
I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes ...
- 201
0
votes
1
answer
196
views
How to build a DFA that recognizes a language
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Build a ...
- 17
3
votes
1
answer
845
views
Prove that determining if a PDA has an infinite language is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given $$\...
- 201
1
vote
0
answers
53
views
Prove that the problem of CFG producing epsylon is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given $$\...
- 201
0
votes
2
answers
2k
views
Show that ALL DFA is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given $$\...
- 201
4
votes
2
answers
1k
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 ...
- 201
0
votes
0
answers
35
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
1
answer
497
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 ...
- 217
6
votes
2
answers
488
views
Do all Turing-complete programming languages have to contain infinite loops?
Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below:
Conjecture. There does not exist a set $...
0
votes
1
answer
255
views
Prove that EXIST = {$<M>$:There exists a string $w ∈ Σ*$ such that $M$ halts on $w$} is undecidable
This is a question by my professor Z. Luria in my Computability course.
My first approach was to try and prove it by contradiction, assuming that EXIST is decidable and using the algorithm that ...
- 217
1
vote
0
answers
40
views
In how far is an automaton allowed to grow based on the length of its input?
Recently, I've written a draft article on the computational power of Petri-nets.
An understanding of Petri-nets isn't really
essential to answering this question, but I'll still note
that the ...
- 11
1
vote
1
answer
46
views
Is the following language in RE?
Given a language $A \in RE$, is the following language also in $RE$?
$$
L_{10}^{A} = \{ \langle M \rangle : \lvert A \cap L(M) \rvert \geq 10 \}
$$
Where $L(M) = \{x \in \{0, 1 \}^* \mid M \text{ ...
- 13
1
vote
0
answers
49
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 ...
- 368
0
votes
0
answers
187
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 ...
- 195
2
votes
1
answer
185
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 ...
- 21
0
votes
0
answers
51
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 ...
0
votes
1
answer
75
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$ (...
- 153
1
vote
0
answers
217
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 ...
- 368
0
votes
1
answer
590
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
1
answer
100
views
Why is the language containing the Turing machines which only accept their own encoding not applicable to the diagonalization proof?
I saw this question and asked myself why the original problem is not solvable through diagonalization. Let
$$L = \bigl\{\langle M \rangle \mid L(M) = \{\langle M\rangle\}\bigr\}$$
Take the complement $...
- 13
1
vote
1
answer
46
views
Which abstract machine or language is exactly expressive enough to produce the computable functions?
I'm interested in software verification and therefore only interested in algorithms which always terminate in predictable amount of time and can determine whether the final result is expected or not, ...
- 165
3
votes
0
answers
155
views
Hopcroft & Ullman: 1969 vs. 1979
How do the 1969 and 1979 books by Hopcroft & Ullman compare? Was the 1969 book an earlier version of the 1979 book?
1969: Formal Languages and their Relation to Automata
1979: Introduction to ...
- 131
0
votes
1
answer
109
views
For every language $L_1$, there exists a language $L_2$ such that $L_2$ is not mapping reducible to $L_1$
I've tried approaching this problem by contradiction, but that did not lead anywhere. Now I am attempting a proof by construction.
i.e. given a language $L_1$, construct a language $L_2$ that cannot ...
- 11
2
votes
1
answer
129
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, ...
- 407
1
vote
1
answer
33
views
Buchi arithmetic meaning
I am studying this article. But I have trouble with understanding the Buchi arithmetic. It says in section IV:
... Formulas in this fragment generalise classical integer programming and are of the ...
- 113
1
vote
1
answer
63
views
Doesn't the Riemman series theorem imply that any real number is computable?
For clarity, I'm talking about this theorem. My confusion lies at the fact that we can seemingly compute any real number by re-arranging a conditionally convergent infinite series, but apparently we ...
