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)

2
votes
1answer
45 views

$A_n$={$x \in \mathbb{N}\mid n \in W_x $} and computation questions?

I‌ prepare for Final-Exam on Complexity Course. in one of my prof. old-exam I see this question: Suppose $A_n$={$x \in \mathbb{N}\mid n \in W_x $}. Which of them is false? 1) Set $A_n$ for each ...
3
votes
1answer
232 views

Arithmetical hierarchy and complexity course note?

In my note, our professor talk about Arithmetical hierarchy. at the end he wrote all of these is True. My main problem is how these are True? ($N$ means Natural ...
-4
votes
2answers
106 views

Why there is no recursive enumerable set such as B that: > $B \nleq_m K$?

I get stuck in one fact that I see on old-mid exam. Why there is no recursive enumerable set such as B that: $B \nleq_m K$ Def: K means Halting Set and $ ...
-4
votes
1answer
109 views

is there infinite functions that satisfy condition of $ S_m^n $ theorem, Be Tautology? [closed]

We know snm-Theorem or $ S_m^n $. I read one Lemma on my note that wrote, http://www.mathematik.tu-darmstadt.de/~streicher/LOGIK2/turi.pdf There is infinite functions that satisfy condition of $ ...
3
votes
1answer
114 views

Can the empty set be an index set?

I ran into a question, encountered in a computational course. Could anyone tell me why the empty set $ \emptyset $ can be an index set? My source is this book
0
votes
1answer
76 views

Creative and Simple Set and $S \leq_m C$? [closed]

I see in an old-exam that wrote if C is a Creative Set and S be a Simple Set we have: $S \leq_m C$ (i.e. m: many to one reducible ). How we can conclude this?
-1
votes
1answer
152 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
67 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
40 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
41 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
32 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
93 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
108 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
63 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
57 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
46 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 ...
1
vote
0answers
23 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
33 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
29 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
30 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
57 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
39 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
48 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
49 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
35 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.
7
votes
2answers
252 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
61 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
28 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
39 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
47 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
60 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
22 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
32 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
25 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
233 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
53 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
77 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
94 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
52 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
51 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
34 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
94 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\}^{*} | ...