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

learn more… | top users | synonyms

-1
votes
0answers
18 views

primitive recursive( course of values recursion)

If $f(n)$ is any function, we write $f(0)=1,f(n)=[f(0),f(1),...f(n-1)]$ if $n\ne 0$ and let $f(n)=g(n,f(n))$ for all $n$. Show that if $g$ is recursive so is $f$. I don't want anybody solve this ...
0
votes
0answers
46 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
64 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
39 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
251 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
79 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
132 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
52 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
55 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
74 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
112 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
79 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
39 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
51 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
57 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
41 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
4answers
177 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
68 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
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 ...
0
votes
2answers
100 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
183 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
60 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
70 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
41 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 ...
-1
votes
3answers
92 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
74 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
34 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
57 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
61 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
407 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
48 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
184 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
66 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 ...
0
votes
2answers
134 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 , ...
4
votes
1answer
109 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
933 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
461 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
109 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
57 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
37 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
41 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
120 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
64 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
90 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
1
vote
2answers
64 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
70 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 ...