Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,915
questions
2
votes
1
answer
40
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
25
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
19
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
22
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
40
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 ...
- 456
0
votes
1
answer
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
0
votes
0
answers
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
1
answer
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 ...
- 11
0
votes
1
answer
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
1
answer
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 ...
- 125
1
vote
0
answers
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
2
votes
0
answers
31
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
61
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
0
votes
2
answers
198
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 ...
- 1
1
vote
1
answer
63
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 ...
- 221
1
vote
1
answer
51
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 ...
- 161
0
votes
1
answer
53
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
88
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
41
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 $Σ^*$...
- 117
1
vote
1
answer
120
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 ...
- 133
1
vote
2
answers
71
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
0
votes
0
answers
52
views
Prove that a subset of $\Sigma^{*}$ is recursively enumerable if and only if it is the range of a partially computable function?
I was assigned the following question for my course on Computing Theory:
Take $\Sigma = \{0, 1\}$. Prove that $ S\subset \Sigma^{*}$ is recursively enumerable if and only if $S$ is the range of a ...
1
vote
1
answer
57
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
124
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 ...
0
votes
0
answers
21
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
102
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 ...
- 181
0
votes
0
answers
40
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
1
vote
0
answers
123
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 $$\...
- 181
1
vote
0
answers
47
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 $$\...
- 181
0
votes
0
answers
89
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 $$\...
- 181
4
votes
2
answers
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
0
votes
0
answers
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
1
answer
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
4
votes
2
answers
112
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
50
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 ...
- 117
1
vote
0
answers
36
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
38
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
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 ...
- 358
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 1
0
votes
0
answers
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 ...
0
votes
1
answer
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$ (...
- 101
1
vote
0
answers
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 ...
- 358
0
votes
1
answer
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
1
answer
42
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
0
votes
1
answer
38
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, ...
- 143
3
votes
0
answers
84
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
59
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
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
1
answer
24
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