Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

learn more… | top users | synonyms (1)

-1
votes
1answer
168 views

Range or Domain of Primitive Recursive Function? [closed]

We are given that $A$ is R.E set. I think all of the following are equivalent to that: (1) A is the range of one primitive recursive function, (2) A is the domain of one strictly increasing ...
0
votes
1answer
42 views

A={$i+1 | i \in N \varphi_i(1393)=2015 $} is Recursive?

I see that my prof. wrote: A={$i+1 | i \in N \varphi_i(1393)=2015 $} is Recursive, but B={$n^2 + n | n \in N \varphi_n(n)= \uparrow $ } is not an r.e set. Who can learn me, about this two example?
1
vote
1answer
65 views

Some questions about Church's Theorem

On page.238 of Enderton's "A Mathematical Introduction to Logic", Church's Theorem is stated (The set of Gödel numbers of valid sentences (in the language of R) is not recursive.) My question is ...
3
votes
1answer
70 views

Is there a Turing Machine that can distinguish the Halting problem among others?

Can there be a Turing machine, that given two oracles, if one of them is the Halting problem, then this machine can output the Halting problem itself? Clearly, if the first oracle is always the ...
3
votes
1answer
48 views

What is the least ordinal $\beta$ for which the function $f_\beta(n)$ in fast-growing hierarchy is incomputable?

Fast-growing hierarchy consists of a transfinite succession of faster growing functions $f_\alpha$: $f_0(n) := n+1$, $f_{\alpha+1}(n) := f^n_\alpha(n)$, $f_{\alpha}(n) := f_{\alpha[n]}(n)$ if ...
0
votes
1answer
43 views

Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ [closed]

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True? a) A and ...
1
vote
2answers
44 views

Recursion, Truncation, and “coding.”

The example is "left to the reader", but I am having trouble approaching this problem. There is a primitive recursive function $tr$ such that if $s$ codes a sequence $(a_{0},...,a_{n-1})$, and $m\le ...
1
vote
1answer
34 views

Showing the “converse” of a relation is semirecursive.

I feel that I intuitively understand why this statement is correct, and I "think" I can explain it, but I don't know how to make it rigorous. I will show the problem, explain what I think the ...
5
votes
0answers
96 views

Path to categorical realizability theory

I'm trying to understand the sorts of things found on this page: http://ncatlab.org/nlab/show/realizability In particular, I want to read Oosten's Realizability: An Introduction to the Categorical ...
4
votes
1answer
146 views

Is there a relationship between Turing's Halting theorem and Gödel Incompleteness

Turing's proof that a Halting oracle is impossible and Gödel's proof that and omega-consistent first order theory of arithmetic must be incomplete are similar in that they use self-referential ...
0
votes
1answer
79 views

Dedekind Cuts and Computable Numbers

Can someone please tell me where I'm wrong? I'm not able to figure out where is the error: First let's define what a computable number is: a number is computable if there is a Turing Machine that ...
2
votes
1answer
64 views

Are there any Martin-Löf random reals that are computable?

For example, Chaitin's constant is both Martin-Löf random and uncomputable. Are there any examples of numbers that are Martin-Löf random but computable?
1
vote
1answer
52 views

Showing that a set is primitive recursive.

I've been having a lot of difficulty even beginning this problem. I believe that I would have to use the min and max functions, but I'm not entirely sure how to actually write this down rigorously, or ...
0
votes
0answers
27 views

Enumerating general recursive functions with a primitive recursive function

I am reading "Set Theory and the Continuum Hypothesis", a monograph by Paul Cohen. In the preliminary chapter, he gives a proof that not all recursively enumerable sets are recursive. He begins by ...
1
vote
1answer
35 views

Show that the language is regular - Closure

For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $$L=\{w \ \mid \ w=a_1 b_1 \dots a_k b_k, \text{ where } a_1 \cdots a_k \in A \text{ and } b_1 \cdots b_k \in B, ...
0
votes
1answer
32 views

Show that the language is regular

Let $$B_n=\{a^k \ \mid \ k \text{ is a multiple of } n\}$$ Show that for each $n \geq 1$, the language $B_n$ is regular. $$$$ Could you give me some hints how we coukd show this?? Do we have ...
0
votes
1answer
33 views

Construct the DFA of the language

I have to construct a DFA for the language $$\{w \mid w \text{ has exactly two } a's \text{ and at leat two } b's\}$$ To construct it we have to construct first the DFA's for the languages $$\{ w ...
1
vote
1answer
31 views

The rationale behind the oracle machine notation with brackets $\{e\}^A$

I would like to understand the rationale behind the oracle machine notation with brackets $\{e\}^A$ which is equivalent to $\phi_e^A$ where $A$ denotes the oracle set and $e$ denotes the index of the ...
3
votes
0answers
67 views

Do there exist a pair of 'orthogonal' non-halting Turing machines?

I'll explain what I mean by orthogonal, which is probably a poor choice of words on my part. Given two Turing machines $\lambda $ and $\tau$,and two inputs $i$ and $j$. lets say $\tau(i) \preceq ...
1
vote
0answers
40 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
2
votes
1answer
49 views

Proof of the Computability of Polynomials

In studying properties of polynomial functions I have read that they are computable. The usage of the word read implies that I cannot prove this statement, and withhold using learned for this reason. ...
1
vote
1answer
54 views

What does Gödel mean by “constant” relating godel definition of recursion to the modern def.

In "On formally undecidable propositions..." he writes a function is recursive if "... it is a constant or the successor function" is he referring to the constant function c(x)=k, and if so, is this ...
0
votes
1answer
36 views

Errata for Rogers' Computability book

I would like to get the errata for the Theory of recursive functions and effective computability by Hartley Rogers, 1987 edition.
6
votes
2answers
254 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
3
votes
2answers
74 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
0answers
33 views

Excel: Paying off hypothetic loan in 25yrs vs 30yrs?

I am attempting to recreate an Excel Spreadsheet Dynamic Model (Figure 9.4) presented in my Data Warehousing Decision Support System course. I've uploaded a copy at the following link: Excel Link - On ...
2
votes
0answers
40 views

Is the probabilitistic distribution of the digits in the Chaitin's constant computable?

The Chaitin constant can in principle be computed with exponential effort on each sucessive digit by brute forcing all programs of a given length and simply proving special theorems on each case that ...
2
votes
1answer
56 views

Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable. I know this theorem - A language is decidable iff both it and its complement are ...
3
votes
1answer
61 views

Axioms defining a Turing machine

I have found the following characterisation in axiomatical terms of a Turing machine: $Q_0(q)\rightarrow T(q)$ $S_0(x)\rightarrow S(x)$ $C(x)\rightarrow S(x)$ $Q_0(q)\land T(qx)\land ...
0
votes
1answer
45 views

Decision Problems and Poly Time

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial ...
1
vote
1answer
24 views

Language described by inverting accepting states of NFA

What is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states. Is there a ...
1
vote
1answer
34 views

$f \in \Sigma_n^1 \iff f \in \Pi_n^1$ in an analytical hierarchy

The proposition 1.7 in Higher Recursion Theory by Sacks states $f \in \Sigma_n^1 \iff f \in \Pi_n^1$ with the proof: Since $f$ is a function, then, $f(x)=y \iff \forall z. [y \neq z \implies f(x) ...
0
votes
1answer
29 views

What is a regressive set?

Several authors (e.g. Jockusch, Appel, McLaughlin) use a notion of a regressive set, however none of the authors gives a complete definition, they refer to the paper J. C. E. Dekker, Infinite series ...
8
votes
1answer
249 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
3
votes
1answer
60 views

Simple factorials

I've been doing some work with factorials and the normal way of calculating them is simply not working so well. When the numbers get really big, doing iterative multiplications is not viable and gets ...
1
vote
3answers
96 views

Examples (trivial and non-trivial) of computable functions whose inverse is not computable

Can you give some examples (some trivial and some non-trivial) of computable functions whose inverse is not computable?
4
votes
2answers
110 views

Is $\Delta_0=\Delta_1$ in arithmetical hierarchy?

I have seen a definition (e.g. http://www.math.ubc.ca/~bwallace/ArithmeticalHierarchy.pdf) of an arithmetical hierarchy in computability starting with: "let $\Delta_0=\Sigma_0=\Pi_0$ be the set of all ...
3
votes
2answers
54 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
1
vote
0answers
52 views

A computable set of sentences neither probable nor disprovable from $PA$

I need to prove that, given a computable binary tree $T$ whose paths are exactly the complete extensions of $PA$ (via some Gödel coding), there is a computable $X\subseteq\mathbb{N}$ such that for all ...
1
vote
1answer
69 views

When is a total $F:\omega^\omega\rightarrow\omega^\omega$ said to be recursive?

Let $F:\omega^\omega\rightarrow\omega^\omega$ be a total function. According to definitions given by Sacks (Higher Recursion Theory) and Rogers (Theory of Recursive Functions) regarding recursive ...
0
votes
1answer
21 views

If a set $\Sigma$ of alphabets is of cardinality $k$, does $\Sigma^n$ have cardinality of $k^n$?

As title says, if a set $\Sigma$ of alphabets is of cardinality $k$, does $\Sigma^n$ have cardinality of $k^n$? This seems to be the case because for each character of the string of length $n$, you ...
0
votes
1answer
36 views

Proving that there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ that is not URM-computable.

I'm trying to prove the statement given in the question title, and I'm unsure as to whether my approach is valid. A confirmation of my approach or a correction with a hint pointing me in the right ...
1
vote
1answer
105 views

There exist uncomputable integer numbers?

This question came from the answer I've given to the question An easy example of a non-constructive proof without an obvious "fix"?. Rereading my answer I had some doubt about the ...
2
votes
0answers
36 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
1
vote
1answer
64 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
0
votes
1answer
32 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
1
vote
2answers
78 views

turing machine with exactly 42 states / state that is visited at least 42 times

I am trying to solve the following problems: Proof wether the following problems are decidable/undecidable: Given turing machine M: Does M have exactly 42 states? Given turing machine M: Does M ...
2
votes
1answer
66 views

Recursively enumerable sets are domain of partial recursive functions

My definition of recursively enumerable set is that it is the language recognized by some Turing machine. I want to show that this definition is equivalent to "a r.e. set is the domain of some ...
2
votes
1answer
76 views

Computable function with noncomputable set of fixed points

I'm looking for a computable function $f: \mathbb{N} \to \mathbb{N}$ such that the set of fixed points $\mathcal{F}_f = \{ e \in \mathbb{N} \mid f(e) \sim e \} = \{e \in \mathbb{N} \mid \forall x \in ...
3
votes
1answer
94 views

Applications of computer science to mathematics

I have been introduced to algorithms, computability and computational complexity (as part of my minor in CS). What are some mathematical topics that I can tackle with the new perspectives I ...