Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
2,055
questions
6
votes
4
answers
1k
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: ...
- 202
1
vote
1
answer
339
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?
- 13
2
votes
1
answer
736
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 ...
- 152
1
vote
2
answers
331
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 ...
- 499
2
votes
0
answers
267
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,276
3
votes
2
answers
326
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 ...
- 381
1
vote
3
answers
2k
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
...
7
votes
2
answers
3k
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 ...
- 71
4
votes
1
answer
2k
views
A language is Turing recognizable iff it is a projection of a decidable language
I was wondering how to prove that a language $C$ 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 know how to ...
- 129
6
votes
1
answer
564
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 ...
- 19.5k
2
votes
2
answers
749
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
2
answers
2k
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 ...
- 69
0
votes
1
answer
110
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 ...
- 105
0
votes
1
answer
247
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 [ x_{ij}.\sum_{k=1}^{m}\sum_{...
- 105
4
votes
2
answers
692
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 ...
- 669
4
votes
1
answer
992
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 ...
- 103
3
votes
1
answer
2k
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 ...
- 33
7
votes
3
answers
591
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 ...
- 377
7
votes
1
answer
984
views
Does Church-Turing thesis also apply to artificial intelligence?
By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem.
Does the word algorithm in this context include artificial
intelligence or not, that is, does ...
- 1,529
-2
votes
1
answer
99
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:
...
- 15
9
votes
2
answers
6k
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,529
0
votes
1
answer
180
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)$ also ...
- 21
1
vote
1
answer
13k
views
Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$
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 ...
- 11
9
votes
1
answer
5k
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 ...
- 377
-1
votes
1
answer
50
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.
3
votes
1
answer
78
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 $\left|l(x)\...
- 213
9
votes
2
answers
619
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", ...
- 535
1
vote
0
answers
69
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". (wiki:http://en....
- 11
2
votes
1
answer
894
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?
- 153
1
vote
2
answers
285
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,529
1
vote
2
answers
97
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 $A$...
- 1,529
1
vote
1
answer
86
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 ...
- 47
1
vote
1
answer
320
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 ...
- 47
9
votes
4
answers
1k
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 ...
- 535
1
vote
5
answers
4k
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 problem....
2
votes
1
answer
315
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 ...
- 47
0
votes
1
answer
229
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 ...
- 1,529
0
votes
2
answers
338
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 ...
- 1,529
5
votes
1
answer
209
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 ...
- 535
-1
votes
1
answer
55
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 ...
- 3
7
votes
1
answer
15k
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 ...
- 81
-1
votes
1
answer
327
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 ...
- 1,529
12
votes
3
answers
3k
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. ...
- 131
3
votes
1
answer
340
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,013
2
votes
0
answers
1k
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$ ...
- 13.4k
3
votes
2
answers
492
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 y}$ $...
- 1,529
7
votes
2
answers
3k
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 ...
- 471
-1
votes
1
answer
3k
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? ...
