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

learn more… | top users | synonyms

0
votes
0answers
2 views

How to post status on twitter user's behalf

I've been trying to create an app to post on the behalf of users to twitter, but am having trouble authenticating. From what I understand, I require the consumer key and secret consumer key for each ...
0
votes
1answer
9 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 ...
0
votes
4answers
70 views

The Halting Problem

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 ...
-1
votes
0answers
32 views

Follow-up question to: Problems that ask whether a language is R.E

$L = \{P : P(n)$ outputs $n^2$ for all $n \in N\}$ $TOTAL=\{P : P(n)$ halts on every input $n \in N \}$ In a previous post, I asked whether "outputs" meant "halts and outputs". The response was ...
3
votes
2answers
63 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 ...
-1
votes
0answers
32 views

Is the set of context-free grammars that describe regular languages decidable?

Consider the language $\qquad\displaystyle L = \{\langle G \rangle \mid G \in \mathrm{CFG}, L(G) \in \mathrm{REG}\}$ My intuition says that $L$ is a decidable language, but I cannot find an ...
-2
votes
1answer
15 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 ...
-1
votes
0answers
14 views

$L=${$a^n ww^R b^n$ | $ w \in (a+b)^+ $} [duplicate]

I read that $L=${$a^n ww^R b^n$ | $ w \in (a+b)^+ $} is Context free. any hint or idea for draw a PDA or CFG? thanks to all.
0
votes
2answers
93 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 ...
-2
votes
0answers
10 views

PRC class Challenging Problem

We know that these fact are true. The class of primitive recursive functions is a subset of every PRC class. Every function in a PRC class can be derived from the initial functions ...
4
votes
2answers
148 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 ...
-1
votes
1answer
53 views

are there any decidable problems not verifiable in polynomial time?

As I understand it NP requires a solution to be verifiable in polynomial time. Can you provide examples of solvable problems not verifiable in polynomial time ?
6
votes
1answer
65 views

Is Post's Correspondence Problem decidable with fixed word size?

So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$. I'm wondering, can anything similar be said for when there is a fixed word length? To be precise, here's ...
3
votes
1answer
38 views

Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that ...
-2
votes
0answers
31 views

Why is it not decidable if a TM writes a given symbol?

The problem Does a TM M on input w ever writes a particular symbol on its tape? is undecidable but we can always check if the TM ever writes that particular symbol on the tape when input string ...
-1
votes
3answers
87 views

If Halting problem is decidable, are all RE languages decidable? [closed]

Assume the halting problem was decidable. Is then every recursively enumerable languagerecursive?
1
vote
2answers
60 views

Can an intersection of two context-free languages be an undecidable language?

I'm trying to prove that $\exists L_1, L_2 : L_1$ and $L_2$ are context-free languages $\land\;L_1 \cap L_2 = L_3$ is an undecidable language. I know that context-free languages are not closed ...
1
vote
1answer
33 views

Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made: 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, ...
0
votes
1answer
50 views

Why is $A_{TM}$ reducible to $HALT_{TM}$?

In Sipser, there is a proof I don't understand. First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input. ...
4
votes
1answer
57 views

Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak

The book Computational Complexity: A Modern Approach by Arora/Barak provides the following: Theorem 1.10 There exists a function $UC: \{0,1\}^* \to \{0,1\}$ that is not computable by any TM. ...
4
votes
3answers
386 views

Rice's theorem vs Turing completeness

I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness. This is the problem: In building an Universal Turing Machine to emulate another ...
-2
votes
1answer
43 views

Neural Network Design Challenge

i'm studying for PHD Entrance Exam on Stanford. one of previous material exam designed very challenging. i want to design a NN for classifying following 2-class problem. 1) output should be -1 or ...
3
votes
3answers
150 views

Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]

Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an ...
1
vote
1answer
63 views

What does it mean for a function to be decidable? (homework)

Note: This is part of a homework exercise. I am asking for clarifications, not a solution! Given: Assume $g: \mathbb{N} \mapsto \mathbb{N}, g\in R$ ($R$ is the class of recursive functions) is a ...
1
vote
2answers
106 views

Theory of computation introductory curriculum

I want to study theory of computation on my own, so I am looking for books. What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation? ...
0
votes
1answer
40 views

Two functions which can create any computable function by composing?

Do there exist two computable functions, a and b, which can construct every computable function by a finite serie of a's and b's which is function composed? Fx. let's take the serie, a,b,a,b,b,a,a,a , ...
3
votes
1answer
98 views

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
7
votes
3answers
916 views

Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?

When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things? For the Halting ...
4
votes
5answers
458 views

Can we use domains other than the naturals in computability theory?

I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia. Can its domain be any countable set rather than $\mathbb N$? Can its domain be an ...
1
vote
1answer
108 views

Is there a problem that cannot be represented using graph?

It is obvious that the representational power of graphs are huge. Is there a problem that cannot be represented using graph? I have recently asked this question to my students and no answers came up. ...
1
vote
1answer
46 views

Is the length of the shortest quine in a programming language computable?

The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of ...
0
votes
1answer
36 views

Demonstration that every finite set is computable [closed]

What is the best demonstration that show that "Every finite set is computable"? thanks
0
votes
1answer
40 views

Confusion in Reducibility

In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM We let R be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following ...
0
votes
0answers
21 views

How can rank set of concepts

I have a concept (for example, "cat") that occurs in 3 out of 5 documents d1, ..., d5. For example: "cat" occurs 3 times in ...
1
vote
3answers
104 views

Is $L_p$ decidable when p is a trivial property?

If $\qquad\displaystyle L_p = \{ \langle M \rangle : p \in P(L(M)) \text{ s.t. } p \text{ is a specific trivial property} \}$, where a trivial property is a property that is shared by all ...
4
votes
1answer
63 views

Showing that a Particular Word Problem is Decidable

I need to give an algorithm to show that the word problem in the group $\langle x,y \mid \mid x^{1984} = y^{2014} = 1 \rangle$ is decidable. How do I show this? I'm not too sure where to start.
3
votes
0answers
85 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
0
votes
2answers
49 views

Reducing A(TM) to some decidable problem

We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable? I couldn't find an example or theory. Thanks
2
votes
2answers
68 views

Is there a name for defining recursive functions as an infinite list of input/output pairs?

Recursive functions are usually defined by directly calling a function inside its own body. Nat = Z | S Nat double Z = Z double (S x) = S (S (double x))) What ...
3
votes
1answer
79 views

Is there a largest class of halting programs?

The halting problem says that a Turing machine cannot decide if another Turing machine halts. However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO ...
1
vote
1answer
39 views

What is the difference between turing reductions and many-one reductions?

To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is ...
5
votes
1answer
159 views

Turing-unrecognizable language - what TM does?

I have a problem giving "intuitive" explanation to turing-unrecognizable languages. We can prove that, say, ${\overline{A_{TM}}}$ is not turing-recognizable, because that would make ${{A_{TM}}}$ ...
0
votes
1answer
42 views

How can a problem be undecidable yet enumerable? [duplicate]

How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers ...
0
votes
1answer
33 views

How can an LBA check legality of TM transitions without extra memory?

In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$. The reduction is proposed in the following manner: we receive a TM $M$ and a ...
2
votes
1answer
98 views

Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
1
vote
1answer
50 views

Need of reducing problems if we already know that a problem is undecidable

In the Reducibility chapter of Sipser's Theory of Computation book, an example is: We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is ...
1
vote
1answer
67 views

Reducibility in Computability Theory

In Sipser's book of Theory of Computation, related to Reducibility, it's written if A is undecidable and reducible to B, B is undecidable. The confusion is, only a solution to B determines a ...
2
votes
1answer
157 views

Is there C++ code that takes infinite time to compile?

Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?
4
votes
2answers
132 views

Is the complexity class NP computably enumerable?

The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing ...
1
vote
2answers
134 views

What is the significance of primitive recursive functions?

I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive ...