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

learn more… | top users | synonyms

2
votes
0answers
11 views

What are the simplest first-order logic statements (in terms of the number of quantifier blocks / object types being quantified) that are undecidable?

This question is a follow-up (on David Richerby's advice) to my earlier question: What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete? Consider a $\prod_x^y$-complete or ...
0
votes
1answer
78 views

How can I learn about CS? [on hold]

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
43 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
25 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
32 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
1answer
17 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
17 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}\,$?
-1
votes
1answer
28 views

Proof that there is no program to verify statements about natural numbers [closed]

Wikipedia briefly mentions that the halting problem implies that there is also no program that can verify statements about the natural numbers. I would be interested to see a proof of this, and how ...
6
votes
2answers
87 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
25 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
54 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
44 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
24 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
41 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
180 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 ...
3
votes
2answers
123 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
33 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
186 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
552 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
39 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
17 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
29 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
58 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
17 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
46 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
123 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
89 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?
60
votes
9answers
12k 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
12 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. ...
0
votes
1answer
73 views

Is the identity function a many-one reduction from a language to super-set?

I need help with a question. Prove or disprove the following claim: Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be ...
2
votes
1answer
38 views

Is concurrent language CCS or CSP turing-equivalent in language power?

Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines? Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?
1
vote
1answer
109 views

Prove Σ* is decidable

I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable. What is the proof that Σ* is decidable?
1
vote
1answer
17 views

Can we obtain a state diagram of a single Turing machine

When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different ...
3
votes
1answer
183 views

Could two decidable languages ever not have a mapping reduction?

Is it ever the case that two decidable languages $L_1$ and $L_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are ...
0
votes
2answers
69 views

What is the definition of a problem

In computation theory, when talking about the computability and complexity of a problem, what is the definition of a problem? How specific should a problem be? For example, can the followings all ...
3
votes
2answers
64 views

Is Newton's Method to compute the zeros of a function an algorithm?

Looking for Newton's method in Wikipedia, I read the following: In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, ...
3
votes
1answer
24 views

Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, ...
5
votes
1answer
216 views

Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
3
votes
2answers
164 views

Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape ...
2
votes
3answers
88 views

Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one: $AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$ Is $AlwaysHalt$ recursively enumerable? I would say YES and ...
2
votes
2answers
97 views

Is it possible to obtain a total function by composition of partial functions?

This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis: If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., ...
3
votes
1answer
258 views

What is a partially computable function?

In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two: A partial function is said to be partially computable if it is computed by some program. and also ...
1
vote
0answers
58 views

Language accepted by a RAM

Show that any language accepted by a RAM can be accepted by a RAM without indirect addressing. Could you give me some hints what I could do??
2
votes
1answer
71 views

Is there a class of formal grammars that generate Recursive Languages only?

Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.) If so what kind of production rules/restrictions do ...