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

learn more… | top users | synonyms

0
votes
0answers
10 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
51 views

Algorithm to compute a recursive function on a given set

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
37 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 [ ...
3
votes
2answers
130 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
92 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
33 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
109 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
63 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 ...
-1
votes
1answer
63 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
78 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 ...
-2
votes
0answers
12 views

Proving that a language is not co-RE but not RE [duplicate]

Let $A = \{ (M,N,w) \mid M\text{ and }N \text{ are TMs and exactly one of them accepts }w \}$. So, in particular, if $(M,N,w)\in A$ then $L(M)\neq L(N)$. Here is how I have shown that $A$ and its ...
0
votes
1answer
81 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)$ ...
1
vote
0answers
40 views

Satisfiable, Complete, Decidable on one Strange Set? [closed]

Why the following question is True? it's noted by my professor without any detail !! Set: {$(p_i \vee $~ $p_{i+1}$$) $$: i \in \mathbb{N}$ } Is Satisfiable, Complete, Decidable, and set of ...
0
votes
1answer
46 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
72 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
17 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
126 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
35 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
102 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?
0
votes
1answer
31 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
46 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
51 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
21 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
134 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
93 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
41 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
48 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
47 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 ...
5
votes
1answer
92 views

Decomposition of the set of computable functions into base functions

Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by ...
-1
votes
1answer
50 views

Some Algorithm on Decidablitly [closed]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
0
votes
0answers
63 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
0
votes
1answer
37 views

What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about ...
7
votes
3answers
994 views

Does the proof of undecidability of the Halting Problem cheat by reversing results?

I have trouble understanding Turing's halting problem. His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. ...
3
votes
1answer
62 views

(Un)Decidability of disjoint decidable and undecidable sets

I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable? I am almost sure that it is ...
1
vote
0answers
27 views

Decidable non time constructible function

Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ ...
2
votes
2answers
77 views

Primitive recursive functions and unbounded quantifiers

From what I know If the predicate $P(t,x_1,...,x_n)$ belongs to some PRC class $\zeta$ then so do the predicates $(\forall t)_{\le y}$  $P(t,x_1,...,x_n)$ $(\exists t)_{\le ...
4
votes
2answers
1k views

What is 'halting'?

I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just ...
-1
votes
1answer
61 views

Let A,B be languages. If A is decidable and B undecidable, then A reducible to B

So I'm learning for an upcoming exam and there's a specific problem which I can't show: Let A be decidable and B undecidable, then $A \le B$ Can someone give me a hint how to solve that? ...
3
votes
1answer
73 views

Arbitrary Programs that Halt

I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation. I thought of considering any arbitrary program that halts, as an ...
3
votes
2answers
121 views

Can a quantum computer (theoretically) do things a classical computer (literally) can't?

I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
0
votes
1answer
50 views

Proving that it's decidable whether a TM ever moves on the blank input

I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above. I've got the problem: $$A_{\mathrm{right}} = \{ \left< M\right> | M ...
2
votes
2answers
38 views

will this be decidable or partially decidable?

$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$ Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is ...
3
votes
1answer
51 views

Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only ...
1
vote
1answer
60 views

Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$ I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out ...
0
votes
1answer
21 views

How to prove computational completeness of a variant of P system

I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove ...
0
votes
0answers
41 views

Are all Turing machines recognizable? [duplicate]

Is the language of the set of descriptions of all Turing machines recognizable? I'm thinking not, but I can't quite define why. A language is Turing-recognizable if some Turing machine recognizes ...
2
votes
1answer
129 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...
0
votes
1answer
44 views

Why Halting problem is Recursively Enumerable?

If we take this definition as R.E. set definition (Computability, Complexity and Languages book written by Davis in page 79) $Definition.$The set $B\subseteq N$ ...
1
vote
1answer
37 views

Is Universality Theorem applicable to Halting problem? [closed]

This is Universality theorem In the Computability, Complexity and Languages book written by Davis in page 70: If $\phi^{(n)}(x_1,...,x_n,y) = ...