Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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)\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
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 $Σ^*$...
user avatar
  • 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 ...
user avatar
  • 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}...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 <...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 $$\...
user avatar
  • 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 $$\...
user avatar
  • 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 $$\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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{ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$ (...
user avatar
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 ...
user avatar
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).
user avatar
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 $...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
39