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

learn more… | top users | synonyms

0
votes
1answer
21 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 ...
0
votes
3answers
136 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?
2
votes
1answer
538 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
35 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
13 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
21 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 ...
-2
votes
2answers
40 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
14 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 ...
-1
votes
0answers
26 views

Is it decidable whether a TM modifies the input more than once?

I am having trouble with this problem: Let $P = \{\langle M,w\rangle \mid M \text{ on input } w \text{ modifies the input at most once}\}$. Is P decidable?
0
votes
1answer
50 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
34 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
112 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
75 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?
-1
votes
0answers
36 views

Is the following statement true ? If L is a decidable language and L′⊆L, then L′ is also decidable ? Prove your answer is correct [duplicate]

Is the following statement true ? If L is a decidable language and L′⊆L, then L′ is also decidable ? Prove your answer is correct I can't figure out this question. Any tips ?
61
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
10 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
68 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
36 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
97 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
15 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
174 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
64 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 ...
2
votes
2answers
51 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
215 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
151 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
83 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
91 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$, ..., ...
0
votes
0answers
56 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
69 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 ...
0
votes
0answers
20 views

How to show {n:U(n,x) is defined for all x} is not enumerable

U(n,x) is Gödel universal function, and we need to show {n:U(n,x) is defined for all x} is not enumerable. I do not have any clue right now. Anyone can give me some hint about this question.
1
vote
1answer
42 views

Satisfiability of first-order logic is undecidable?

I struggle with understanding why the satisfiability in the first-order logic is undecidable. Could you explain it with some examples? I've also seen that satisfiability in some first-order formulas ...
2
votes
2answers
257 views

Is this variant of ATM decidable?

Ok so I understand how $\mathrm{ATM} = \{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts $w$}\}$ is undecidable. Is this because $w$ is a variable? What if the parameter is fixed? ...
1
vote
2answers
82 views

Computation is effectively computable in theory and in practice

My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice? In trying to understand these concepts further, I have a couple ...
3
votes
1answer
134 views

Are there more partially recursive functions than and recursive functions?

Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?
6
votes
0answers
53 views

Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...
0
votes
2answers
122 views

Decidability of empty intersection of two languages accepted by Turing machines

I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not. I have a language $\qquad\displaystyle L = \{ (R(M_1), R(M_2)) ...
0
votes
2answers
111 views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...
1
vote
5answers
115 views

Function whose implementation is difficult (computationaly) to work out

Let's say I've got a function $f$ that takes a single number and returns a number. And I have another function $\mathrm{verify}f$ which takes the input I gave to $f$ and the number returned by $f$ ...
-1
votes
2answers
88 views

Extension of Rice's theorem

How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is ...
2
votes
1answer
43 views

How is Rice's theorem applicable to this decision problem?

I recently had a test in introduction to computability and I got the following question wrong. The question Input: A classical Turing machine $M$ with a 2-dimensional tape. output: Does there ...
2
votes
1answer
56 views

Decide if a specific Turing machine halts on a specific string

Can you always decide if a specific Turing machine accepts a specific string? I started thinking about this after reading an answer to this question, Rice's theorem vs Turing completeness, which ...
1
vote
2answers
64 views

A recursively enumerable language and a recursively enumerable set

I am confused between these two terminologies: recursively enumerable language, recursively enumerable set. Do they have the exactly same meaning?
2
votes
1answer
41 views

Converting decision problems to grammars?

I'm struggling to understand some concepts related to the relationship between language and computability theories. Can we convert decision problems to the corresponding grammars describing the ...
0
votes
1answer
46 views

Clarification of Hopcroft's proof that “deciding whether a program halts on all inputs” is not R.E

$DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$ $AlwaysHalt =\{ M : M$ halts on all inputs x $\}$ Hopcroft gives the following proof that $AlwaysHalt$ is not R.E. 1) Given an input ...
1
vote
5answers
273 views

How is Turing's Solution to the Halting Problem Not Simply “Failure By Design”?

I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer. Here is my understanding of the Halting Problem: Let $M$ be the set of all ...
3
votes
2answers
70 views

Does “output” always imply halting in computability?

$L = \{P : P(n)$ outputs $n^2$ for all $n \in N \}$ In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can ...
-2
votes
1answer
16 views

$L \in RE$ Question [closed]

I see a sentence in one final exam on automaton course. I have one problem: if we want to have a TM that halts for all word in L, it's enough to have L be R.E? or we should have R be R.E and ...
0
votes
2answers
107 views

The image of a recursive language under a computable function

Let $f:\Sigma^{*}\to\Sigma^{*}$ be a computable function and let $L$ be a recursive language. Is $f(L):=\left \{{f(w)|w\in L} \right\}$ recursive? Here, I see clearly, that $f^{-1}(L)$ is recursive ...
4
votes
2answers
215 views

Halting problem without self-reference

In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a ...