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

learn more… | top users | synonyms

0
votes
0answers
3 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 ...
0
votes
1answer
66 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
177 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
15 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
27 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 ...
4
votes
2answers
79 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
106 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
67 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 ...
0
votes
0answers
31 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
54 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
236 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
39 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
18 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
29 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
51 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
141 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
50 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
86 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
38 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 ...
1
vote
2answers
53 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
0
votes
1answer
36 views

Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is ...
1
vote
1answer
37 views

Proving a function is uncomputable [duplicate]

I am trying to solve the following problem: For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if ...
5
votes
2answers
2k views

Is 0* decidable?

I found a statement (without explanation) that a language $A = 0^*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite ...
0
votes
2answers
47 views

Relation between sets and partially computable functions

I encountered this problem. Let $A$ , $B$ , $C$ be disjoint sets $(A\cap B = B\cap C = A\cap C = \emptyset)$. The $f_1, f_2$ and $f_3$ are partially computable functions that are defined as ...
1
vote
1answer
18 views

Decidability language, intersection

I have two langages $ A, B \in \mathrm{coRE}$. How can I prove that $ A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\,$?
6
votes
2answers
89 views

Analog of PP for computability rather than complexity?

The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the ...
0
votes
0answers
34 views

Plot of a computable function

Let's denote a total increasing computable function $f: \mathbb{N} \rightarrow \mathbb{N}$. How to prove that the plot of $f$ is a decidable subset of $ \mathbb{N} \times \mathbb{N}$? My solution: 1) ...
0
votes
0answers
27 views

Is it decidable whether a TM accepts more than one word?

Is the following language: $\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$ Turing-decidable? I think it isn't, because if a Turing machine T can ...
4
votes
1answer
58 views

Is the difference of a non-recursive and recursive set recursive?

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...
1
vote
1answer
57 views

If the Halting Problem was solvable, and we solved it, what would be its implications?

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved. What would be the Halting Problem's implications in ...
0
votes
1answer
32 views

Equivalence of Recursively Enumerability (RE) definitions

Let A be a subset of N n Definition1 of RE DEF1_RE = A is RE iff there is a TM M st M(x) = 1 iff x belongs to A, 0/undefined otherwise Definition2 of RE DEF2_RE = A is RE iff there is a ...
0
votes
1answer
27 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
1
vote
1answer
43 views

Is the extension of every undecidable theory undecidable?

While it is not the case that the extension of every decidable theory is decidable, is it true that: the extension of every undecidable theory undecidable? In other words, given an undecidable ...
2
votes
3answers
190 views

Does the normal form theorem imply that every partially computabe function is primitive recursive?

This is Normal Form Theorem (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75): Let $f(x_1,...,x_n)$ be a partially computable function. Then there is a ...
4
votes
2answers
126 views

Prove existence of different programs printing each other code

How to prove that there exist two different programs A and B such that A printing code of B and B printing code of A without giving actual examples of such programs?
1
vote
1answer
29 views

Recovering the transition function of a Turing machine with a known number of states

Suppose we have a Turing Machine and know how many states it has as well as bound on its running time, but do not initially know its transition function. Is it possible to determine its transition ...
1
vote
1answer
65 views

Diophantine equations and P=NP

It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates ...
-2
votes
3answers
192 views

Is every problem in NP solvable?

Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
3
votes
1answer
568 views

What does the set {n | n is an integer and n = n + 1} represent?

I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This doesn't make any sense to me. I ...
2
votes
1answer
41 views

An infinite language with no infinite RE or co-RE subsets?

Are there any languages that are infinite (that is, they contain infinitely many strings) but which do not have any infinite subsets that are RE or co-RE languages? This seems related to simple sets, ...
0
votes
1answer
19 views

Example of reduction such that it is not many-one reduction while it is not turing reduction

I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?
-1
votes
1answer
31 views

Why apply the assumed decide für HALT to the input and its code?

In the lecture notes I have got in class I have the following proof for the halting problem not being recursive Assume $H$ is recursive and TM $M_1$ decides it. Construct $M_2$ that gets ...
0
votes
2answers
60 views

Is emptiness of the intersection of the languages of two TMs decidable? [duplicate]

Let $\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$. How do I know if this language is decidable or not? And How do I prove ...
0
votes
0answers
20 views

Partial recursive characteristic function for finite sets

In class we were told that, for every finite subset $X$ of the natural numbers, it is possible to find a partial recursive function $g(x)$ that outputs $1$ if $x\in X$ and $0$ if ...
0
votes
1answer
55 views

Decide whether DFA have useless states

A useless state in a DFA is one that is never entered on any input string. Consider the problem of determining whether a DFA has any useless states. Formulate this problem as a language and show that ...
0
votes
1answer
48 views

Function is recursive iff its graph is recursively enumerable

So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere. But how to prove that function is recursive ...
-1
votes
2answers
131 views

Is the infinite union of computable sets computable? [duplicate]

My intuition is telling me that this is untrue. But I am having trouble formulating a proof for this. Can anyone point me in the right direction? I've seen a proof by contradiction involving the union ...
-1
votes
1answer
95 views

If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?

If all infinite r.e. languages have an infinite recursive subset, then can we logically take co-r.e. languages to not have such subsets by complemence?
62
votes
9answers
13k views

Why, really, is the Halting Problem important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
-1
votes
1answer
14 views

Cocurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent

In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent. ...