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)

4
votes
2answers
112 views

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined?

How should the relativized Kleene pointclass $\Sigma^1_1(A)$ be defined, when $A$ is a set of reals ($A \subset \omega^\omega$)? I assume that there is a standard definition, but I can't seem to find ...
2
votes
2answers
108 views

Which mistake(s) in my argument re: representability, definability and the halting problem?

I'd like to ask for your help in showing me the (quite likely: several) flaws in my argument below, relating weak and strong representability in a formal system and the halting problem. At least ...
5
votes
2answers
135 views

Do you need true randomness to beat the two-envelope game?

A well-known (non-)paradox in probability involves a two-envelope game played between two players, $A$ and $B$: $A$ selects two distinct (real) numbers, $x$ and $y$, writing each one down on a card ...
1
vote
2answers
26 views

Computability: is there an alternative method to decide this language?

For my computability revision I am trying to decide the language, $$L = \{ \text{all binary strings containing the pattern 001 (not necessarily in consecutive places)} \}.$$ I believe that I can do ...
0
votes
0answers
30 views

Show the following languages are not recursive

Show that the language $$L = \{ M : M \text{ is a Turing Machine that halts on input $M$ } \} $$ is not recursive. Show that the language $$ L = \{M : M \text{ is a Turing Machine such that $L(M)$ ...
1
vote
1answer
69 views

determining recognizable or decidable (TM that accepts a TM)

I'm having an issue determining whether certain languages are decidable, recognizable or neither. The specific languages I'm referring to are of the following form L = {<M> | for every w, M accepts ...
0
votes
1answer
90 views

is differ between distributive lattice vs semi-lattice on Turing Degrees

We know a Posed Closed under suprema but not necessarily under infima is an upper semi-lattice. We now r.e set forms a distributive lattice. But my question is why following statement is hold? I ...
0
votes
1answer
36 views

decidability of a given language

The language EGAL is $\{(A,B): A \text{ and } B \text{ are DFAs with } L(A) = L(B)\}$ How do I prove that such language is decidable by testing every word of $A$ and $B$ until a defined length ? i ...
0
votes
0answers
108 views

Does removing the (1) in $\Phi{(1)}$ affect the proof that $ K_0 \leq_m K$ or not?

The fragment below from Martin Davis' book shows $ K_0 \leq_m K$ and also proves $ K_0 \leq_1 K $. My question is if we remove the $(1)$ of $ \Phi^{(1)}$ in the definition of $Y$ (i.e fifth line in ...
2
votes
1answer
54 views

How to computably reduce the number of colors in (infinite) Ramsey's theorem

Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a ...
1
vote
1answer
84 views

Which way is best to solve: $T(n)=5T(n/5) + n\;?$

I'm not sure which way is best to solve $$T(n)=5T(n/5) + n$$ (recursion tree/master method/recurrence?) I would like some assistance, which way is easier and how can I be sure I got the right answer ...
2
votes
1answer
134 views

Have we found a Turing Machine for which halting/non-halting is unprovable?

The undecidability of the Halting Problem implies that there exist Turing Machines such that you can't prove whether they halt or not in whatever logical system you're using (let's say ZFC)$^1$. Have ...
1
vote
1answer
25 views

strongly hh-immune sets

I'm trying to do exercise X.2.16 from Soare's Recursively Enumerable Sets and Degrees, but I have no idea how ro solve it. Any hints would be appreciated. An infinite set is strongly hh-immune or ...
0
votes
1answer
46 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
1
vote
2answers
67 views

Convert NFA to DFA

I have to convert the following NFA's into the equivalent DFA's. I have done the following: Could you tell me if it is correct??
0
votes
1answer
298 views

Primitive Recursive on Some Functions?

We took an entrance exam on Set and Complexity Course, The question says: if $g$ be a primitive recursive, $1)$ $f_1(0)=c_1, f_1(1)=c_2, ...
-2
votes
2answers
189 views

Set of One-Variable Computable Function and one Local Contest Questions?

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

Are there any known noncomputability proofs that do not rely on the halting problem?

I have looked around and thought of this for a while, and I have not found or been able to construct any proof that a problem is not decidable, without said proof being fundamentally equivalent to ...
1
vote
1answer
63 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...
2
votes
1answer
48 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
243 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
109 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 $ ...
3
votes
1answer
126 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
-1
votes
1answer
92 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
172 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
67 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
71 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
54 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
46 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
35 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 ...
6
votes
0answers
98 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
148 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
87 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
65 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
54 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
40 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
37 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
81 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
42 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
59 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
82 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
37 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 ...