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

learn more… | top users | synonyms

1
vote
1answer
25 views

Universal Turing machine

I'm trying to find the answers of two questions about the Universal Turing machine. 1.How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger ...
2
votes
2answers
25 views

Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of $\{D\mid D\text{ is a DFA and }L(D) = S\}$ and $\{G\mid G\text{ ...
-1
votes
1answer
15 views

Efficient algorithms for finding the limit of a sub-sequence [closed]

Given a sequence $A_N={a_1,a_2,a_3...,a_N}$ of real numbers, and given that there exist some sub-sequence which generated from some deterministic converging sequence. Are there any efficient ...
0
votes
1answer
39 views

Turing Machines and Algorithm for Language Acceptance

Is there an algorithm to decide if any two Turing machines accept the same language? I can't find a definite answer to this. My guess is that there isn't, because then we would be able to decide if ...
-2
votes
0answers
35 views

Do undecidable sounds exist? [closed]

In addition to frequency and amplitude determining pitch and volume, my understanding is that the shape of the waveform defines the timbre of the sounds. A sin wave or square wave make distinct ...
5
votes
0answers
44 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
0
votes
1answer
22 views

If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?

I am discussing with a friend the following question: If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable? I believe it is. My point ...
-2
votes
0answers
18 views

Decidable language properties, L1 - L2

Given two decidable languages, L1 and L2, I have to show whether or not L1 - L2 results in a decidable language. I am not sure how to proceed, I am aware of the closure properties of decidable ...
0
votes
0answers
14 views

Forward jump turing machine and r.e languages [duplicate]

I was going through some exercises I found online and I am really stuck at this problem: Consider Turing Machines with the following restriction: they are only allowed forward jumps, i.e. if ...
3
votes
4answers
539 views

Do we need recursion in programming language to solve any problem?

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions? Assuming we are allowed to use: ...
-2
votes
0answers
15 views

Is quantum Turing recognizability/decidability bigger than (classical)Turing-recognizability/decidability?

How does the set of quantum-Turing recognizable languages compare to the set of Turing recognizable languages? Same question for decidability. Is the former strictly more powerful than the latter?
1
vote
1answer
38 views

If A is decidable and B is decidable, then A is Turing Reducible to B

The statement seems intuitively true but is it? If so, how can I prove this?
1
vote
1answer
42 views

Why does my answer sheet say the set of computable functions is uncountable?

I'm trying to understand why I can't find room for the set of computable functions in the hotel of the Hilbert's Hotel Paradox. I was thinking that, because Gödel numbering, I could consider the set ...
1
vote
1answer
32 views

Trying to understand the proof of the halting problem presented in Sipser textbook

I'm having some problems to understand the classic proof of the halting problem. The Proof: $A_{tm} = ${$<M,w>$ | $M$ is a $TM$ and $M$ accepts $w$}. We assume that $A_{tm}$ is decidable and ...
1
vote
0answers
59 views

A complete catalog of 2-state Turing machines?

For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a ...
3
votes
2answers
84 views

Halting Problem and Turing Degree and Reduction? [closed]

This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question. for $ A \subseteq \mathbb{N}$ we ...
1
vote
3answers
59 views

Language is recursive, hence recursively enumerable

I was going through a book of proof and I read: If L is recursive, L is r.e. And the proof goes: Let L be recursive, hence there is a TM that decides it Convert an halt state to a normal state ...
6
votes
2answers
209 views

Decidability of “Is this regular expression prefix-free?”

Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it ...
2
votes
1answer
64 views

Turing recognizable -decidable languages-

I was wondering how to prove that $C$ (which is a language) is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not ...
2
votes
1answer
40 views

Can a probabilistic Turing Machine compute an uncomputable number?

Can a probabilistic Turing Machine compute an uncomputable number? My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should ...
-1
votes
0answers
32 views

Counting the number of strings generated by a TM

I'm having an issue with the following exercise (roughly translated by me); Given a turing machine $A$, which generates strings over a certain alphabet, and a turing machine $B$ which accepts a ...
2
votes
2answers
107 views

Does “contains only” imply “contains”?

Written in English, does "the set S contains only members of set T" imply that S does contain some member of set T? How would this relationship be written formally?
6
votes
2answers
304 views

Are these sets of indices also index sets?

An index set is a set of all indices of some family of computably enumerable sets. It is known that the empty set is an index set and that $K = \{e \mid e \in W_e\}$ is not an index set. The ...
0
votes
0answers
11 views

Can we compute the fastest algorithm for a given total function? [duplicate]

First let $f$ be the description of a partial function. Let $\operatorname{optimize}(f)$ be a function that returns a description of the "fastest" Turing machine that computes $f$ for some sensible ...
0
votes
1answer
69 views

Algorithm to compute a recursive function on a given set [closed]

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
0
votes
1answer
56 views

Recursive algorithm to compute a sum of product like function

I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows $F_{i,j}(m)=\sum_{t=j}^{m}\left [ ...
4
votes
2answers
144 views

Unprovable Post correspondence problem instance

Since there is no algorithm for the post correspondence problem, there exists an instance of this problem such that we can neither prove that the instance is positive nor prove that the instance is ...
4
votes
1answer
115 views

Primitive Recursion and course-of-values recursion - examples?

I ran into examples that I not trivially understand on course-of-values recursion, In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the ...
0
votes
1answer
43 views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
6
votes
3answers
122 views

Unreachable Real Numbers - Randomness & Computability

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
0
votes
1answer
67 views

Does Church's Thesis include artificial intelligence?

By Church's Thesis it is impossible to design an algorithm to decide halting problem. I would like to know the word algorithm in this context includes artificial intelligence or not? I mean is it ...
-2
votes
1answer
66 views

Are finitely many statements resp. variables sufficient to compute every function?

I prepare for local complexity contest and review some old Interview questions banks. I get stuck in one problem and no idea how we can solve it. please share your idea or help with this question: ...
1
vote
2answers
84 views

Why is Oracle Turing Machine important?

As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design ...
-1
votes
1answer
83 views

Many-one-reductions with finite image

Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$. How can $f(K)$ be a finite set? Why if‌ $B$ is recursive, is $f^{-1}(B)$ ...
0
votes
1answer
104 views

Proving a language is not Turing-recognizable by reduction

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language L is not ...
0
votes
1answer
94 views

Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a ...
-1
votes
1answer
25 views

Definition of co-RE class

I know that the definition of RE class is: $\ RE = \left \{ L \subseteq \Sigma ^{*} | \text{Exists M which accepts L} \right \}$ Can someone explain in the same notation the definition of co-RE.
2
votes
1answer
19 views

Complexity of self-reducible set

I am trying to solve the following problem: A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where ...
6
votes
2answers
138 views

Is there a clear definition of “computable” for models of computation which are not turing complete?

This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", ...
0
votes
0answers
38 views

Relationship between functions and formal languages?

PR is defined as "the complexity class of all primitive recursive functions" and also equivalently as "the set of all formal languages that can be decided by such a function". ...
2
votes
1answer
108 views

Is equivalence of a CFG and an RG undecidable?

I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?
1
vote
2answers
54 views

If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ? it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea ...
1
vote
2answers
48 views

Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If it is true how to prove it? Update It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then ...
1
vote
1answer
54 views

How to prove that there is a function index t so that t³ + t + 1 is an index of the same function?

I would like to prove $\exists t\phi_t = \phi_{t^3+t+1}$ where $\phi_0,\phi_1,\phi_2,...$ are sequence of all of the partially computable function. $\phi_t = \phi_{t^3+t+1}$ only if $t = t^3+t+1$ and ...
1
vote
1answer
22 views

Type of undecidability in Rice Theorem

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. As David Richerby said in here : Undecidable means not decidable. Undecidable problems may or may not ...
2
votes
3answers
137 views

Implications of Rice's theorem

Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong. Lets take some non-trivial property of the set of ...
1
vote
5answers
102 views

How do I show that a DFA accepts only one word?

I want to show that $\qquad\displaystyle O = \{M : M \text{ is a DFA}, |L(M)| = 1\}$. Here $|L(M)|=1$ means the DFA contains only one state. I really don't know where to get started in this ...
2
votes
1answer
42 views

What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
0
votes
1answer
51 views

If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable? what ...
0
votes
2answers
50 views

How to find out if a piecewise function is partially computable?

I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he ...