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

learn more… | top users | synonyms

-1
votes
3answers
61 views

If Halting problem is decidable, are all RE languages decidable?

Assume the halting problem was decidable. Is then every recursively enumerable languagerecursive?
-1
votes
0answers
37 views

Solvable & Unsolvable Problem Detection [duplicate]

be aware that this problem dosnt have solution. I ran into A multiple choice question on previous midterm on Computation Theory course. this question is which of the following problem is not ...
1
vote
2answers
52 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 ...
-5
votes
0answers
62 views

Unsolvable Problem Question [closed]

I Ask this question on Math Section, but the users encourage me to ask it here. The halting problem is the most famous of all unsolvable problems. i try to summarize one list of unsolvable problem. i ...
1
vote
1answer
28 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, ...
-2
votes
0answers
20 views

TCP & UDP time taken/retransmission calculation

What i know is that, TCP provides reliable point-to point communication, whereas UDP doesn't establish a connection before sending data, it just sends. For this question, assuming that for UDP-IPv4 ...
0
votes
1answer
48 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
56 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
380 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
42 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
140 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
61 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
91 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
39 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 , ...
2
votes
1answer
90 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
903 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
104 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
41 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
34 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
37 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
99 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
62 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
80 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
47 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
65 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
78 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
36 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 ...
4
votes
1answer
152 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
41 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
32 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
95 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
48 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
62 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
148 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
126 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
122 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 ...
1
vote
2answers
50 views

Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

Let the following datatype be defined: data T = A | B T | C T T That is, B, B T, B (B T), C A A, C (B T) A and so on all are ...
6
votes
2answers
78 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
3
votes
1answer
86 views

Can every program be turned into a quine?

Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't ...
2
votes
2answers
67 views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
1
vote
1answer
39 views

If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$. Is this true? My intuition is false even if we can find some special case to make it true such as ...
1
vote
1answer
32 views

How do you prove that this TM decides a language that is undecidable? [closed]

In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language $$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w ...
-1
votes
2answers
77 views

Mathematical function vs Computer program

In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration. Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets. Then relation $R \subseteq A_1\times ...
1
vote
2answers
136 views

If a DFA can be simulated by a real program, can it be simulated by a TM

In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says ...
9
votes
1answer
91 views

Computing the intersection of two NPDA where it is possible

Apropois to Raphael's suggestion on Intersection of two NPDAs: Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is ...
1
vote
1answer
62 views

Is the language of TMs that halt on some string recognizable?

I would like to show that the following language is recognizable: $$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$ How do I go about showing that this language is ...
5
votes
2answers
430 views

Is it possible for a language and its complement to both be unrecognizable?

Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable? If some other language $S$ and its complement $\overline{S}$ are both recognizable, ...
4
votes
2answers
469 views

Sandwiching Languages

I am studying for my algorithms final and came across the following problem: Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are ...