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

learn more… | top users | synonyms

1
vote
3answers
41 views

How do I show that a DFA accepts only one word?

I want to show that $\qquad\displaystyle O = \{M : M \text{ is a DFA}, |L(M)| = 1\}$. Here $|L(M)|=1$ means the DFA contains only one state. I really don't know where to get started in this ...
2
votes
1answer
21 views

What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
-1
votes
1answer
32 views

If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable? what ...
0
votes
0answers
25 views

Topics in Computability [on hold]

I am taking the graduate course Computability and at the end of the semester I will have a presentation. The prof told us to chose the topic. Do you have any suggestions??
-1
votes
2answers
43 views

How to find out if a piecewise function is partially computable?

I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he ...
5
votes
1answer
78 views

Decomposition of the set of computable functions into base functions

Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by ...
-1
votes
1answer
49 views

Some Algorithm on Decidablitly [on hold]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
0
votes
0answers
46 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
-3
votes
0answers
35 views

How to prove or disprove that the following is decidable [closed]

{<G,A> : G is a regular grammar and A is an unreachable variable in G} In a CFG G, a variable A is unreachable if there is no derivation S->*w with w ...
-1
votes
0answers
6 views

Java Programming Method Overloading Help [migrated]

First time posting here sorry about the format. public static void main(String args[]) { ...
1
vote
1answer
35 views

What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about ...
-1
votes
0answers
43 views

What are the results of Fixed Point Theorem? [closed]

Here is the fixed point theorem By Davis Let $f(z)$ be a computable function. there is a number $e$ such that $\forall x$  $\phi_{f(e)}(x) = \phi_e(x)$. This theorem seems to be simple and ...
7
votes
3answers
974 views

Does the proof of undecidability of the Halting Problem cheat by reversing results?

I have trouble understanding Turing's halting problem. His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. ...
3
votes
1answer
58 views

(Un)Decidability of disjoint decidable and undecidable sets

I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable? I am almost sure that it is ...
0
votes
0answers
32 views

Showing that a property of a language is trivial [closed]

Given some set of languages with a property, say $$A=\{L \mid L \text{ is the language of some Turing machine that never halts after second step}\}\,,$$ and I need to show that it's a trivial ...
1
vote
0answers
26 views

Decidable non time constructible function

Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ ...
2
votes
2answers
69 views

Primitive recursive functions and unbounded quantifiers

From what I know If the predicate $P(t,x_1,...,x_n)$ belongs to some PRC class $\zeta$ then so do the predicates $(\forall t)_{\le y}$  $P(t,x_1,...,x_n)$ $(\exists t)_{\le ...
4
votes
2answers
1k views

What is 'halting'?

I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just ...
-1
votes
1answer
57 views

Let A,B be languages. If A is decidable and B undecidable, then A reducible to B

So I'm learning for an upcoming exam and there's a specific problem which I can't show: Let A be decidable and B undecidable, then $A \le B$ Can someone give me a hint how to solve that? ...
3
votes
1answer
69 views

Arbitrary Programs that Halt

I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation. I thought of considering any arbitrary program that halts, as an ...
3
votes
2answers
107 views

Can a quantum computer (theoretically) do things a classical computer (literally) can't?

I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
0
votes
1answer
47 views

Proving that it's decidable whether a TM ever moves on the blank input

I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above. I've got the problem: $$A_{\mathrm{right}} = \{ \left< M\right> | M ...
2
votes
2answers
36 views

will this be decidable or partially decidable?

$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$ Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is ...
3
votes
1answer
51 views

Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only ...
1
vote
1answer
59 views

Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$ I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out ...
0
votes
1answer
19 views

How to prove computational completeness of a variant of P system

I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove ...
0
votes
0answers
41 views

Are all Turing machines recognizable? [duplicate]

Is the language of the set of descriptions of all Turing machines recognizable? I'm thinking not, but I can't quite define why. A language is Turing-recognizable if some Turing machine recognizes ...
2
votes
1answer
127 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...
0
votes
1answer
42 views

Why Halting problem is Recursively Enumerable?

If we take this definition as R.E. set definition (Computability, Complexity and Languages book written by Davis in page 79) $Definition.$The set $B\subseteq N$ ...
1
vote
1answer
32 views

Is Universality Theorem applicable to Halting problem? [closed]

This is Universality theorem In the Computability, Complexity and Languages book written by Davis in page 70: If $\phi^{(n)}(x_1,...,x_n,y) = ...
1
vote
1answer
24 views

What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable?

In our lecture notes on lamdba calculus, I encountered the sentence: Let $M$ be a set and $f\colon ℕ → M$ be computable. Does this even make sense? Don’t we need aditional structure on $ℕ$ and ...
1
vote
1answer
98 views

If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?

Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or ...
3
votes
1answer
187 views

What is the exact meaning of a Predicate, decidability and computability?

In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as: By a predicate or a Boolean-valued function on a set ...
-2
votes
1answer
20 views

Language L and its complementary both not recursively enumerable?

Is it possible to proof for a Language L and its L-complemented to be both not recursively enumerable? Can be useful to consider the (Ld) diagonalization Language? thank you.
2
votes
0answers
34 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
-2
votes
1answer
26 views

Decision Problems of Regular languages and CFL's [closed]

Consider the following decidability questions ...
5
votes
2answers
89 views

Are there things an analog computer can do that digital computing cannot do?

The crux of the difference between analog and digital computing is the number of bits of precision available, right? Now, I know that in the Turing machine, numbers can be stored with any degree of ...
3
votes
5answers
112 views

is it possible to minimize pushdown automata?

is it possible to minimize pushdown automata? If no, why? Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
2
votes
1answer
80 views

Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable?

Consider the following langugage: $\qquad L = \{ \langle M \rangle \mid M \text{ TM}, w \in L(M) \implies ww \in L(M)\}$. I've been asked to decide whether this language is in R/RE/CO-RE. I've ...
1
vote
0answers
40 views

Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset

My attempt to solve this: If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and ...
1
vote
1answer
56 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
3
votes
2answers
253 views

Quantum computers and computable functions

A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate? If a function is not computable? Does this mean it ...
1
vote
0answers
49 views

Models of Computation and What they can model [closed]

Some days ago i've discovered that in most of what we call "models of computation ", we can possibly model tasks other than computation itself . For instance, in lambda calculus we can model control ...
0
votes
1answer
19 views

Each finite segment of a noncomputable integer sequence is computable

Wikipedia claims that "each finite segment of noncomputable sequence of integers is computable". It continues to clarify: For any noncomputable function, "for any given value of n, [...] a trivial ...
2
votes
1answer
32 views

What sort of theoretical machine would be needed to solve the tiling problem?

So theoretically, what sort of machine would we need to solve the tiling problem? (Given a set of tiles, decide if they will tile the plane or not.) I know we could have a Turing machine plus a ...
2
votes
1answer
72 views

Using Generalized Rice's Theorem to Prove Decidability

I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to ...
2
votes
1answer
177 views

Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable

I'm trying to answer this question: Let $S$ be the strings $\langle P \rangle$ accepted by the Turing Machine $P$ with input alphabet $\{a,b\}$, where $P$ accepts an infinite number of strings ...
0
votes
2answers
54 views

Separability of languages in RE

Say that a language $C$ is a separator for disjoint languages $A$ and $B$ if $A \subseteq C$ and $B \subseteq \bar{C}$. I need to find two languages $A,B\in \mathrm{RE}$ that have no recursive ...
0
votes
1answer
87 views

How can I learn about CS? [closed]

I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient ...
1
vote
2answers
39 views

Decidable product with an undecidable projection

I got some problems with building a set, which should looks like this: $S = A\times B \subset N \times N $, where $S$ is decidable but $A$ is undecidable. Could somebody give me a clue how ...