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
vote
0answers
16 views

Pointclass of $\text{dom}(F)$ where $F:\omega^\omega\rightarrow\omega^\omega$ is partial recursive.

The definition I am working with: A partial function $F:\omega^\omega\rightarrow\omega^\omega$ is said to be partial recursive iff the partial function $G:\omega^\omega\times\omega\rightarrow\omega$ ...
0
votes
1answer
36 views

Finding the sum of special multiplications

Let $n$ be an integer and $a_1, \dots, a_n$ positive reals. $\forall 1 \leq i < j \leq n$ let $a_{i, j}$ be a positive number. Let $k \leq n$ be a positive integer. I would like to find an ...
4
votes
0answers
26 views

Is there an algorithm that probably solves the Halting problem?

Such an algorithm takes as input any program and returns a probability that it halts. In the limit of many programs, it must answer on average in the correct proportion. But im interested in other ...
4
votes
2answers
78 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 ...
0
votes
1answer
38 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 ...
4
votes
1answer
66 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
16 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
23 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
43 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
75 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
32 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
104 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
42 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 ...
-3
votes
0answers
21 views

Chomsky Normal Form conversion

Given CFG as S->aSbb|T T->bTaa|S|ε I removed the ε rules and the unit production rules but i am getting the next step as S->aSbb|bTaa|baa T->bTaa|aSbb|baa Now how to proceed after this.Please help
1
vote
1answer
53 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 ...
1
vote
1answer
80 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
20 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
34 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
32 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
294 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
177 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
64 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 ...
2
votes
1answer
57 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
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 ...
0
votes
2answers
279 views

Index set definition in Computation Theory

We know index set is a set of all indices of some family of computable [partial] functions/computably enumerable sets. The empty set is a set of computable functions, and the empty set is ...
-1
votes
1answer
172 views

Halting Set and some Tautology Facts !!

We know from computational book, $K$ is a Halting Set Problem as $K=\{e \mid e \in W_e\}$. $W_e$ is the set of inputs for which the program encoded by $e$ halts. Question: I read in the book that ...
-1
votes
1answer
67 views

Turing reducibility and Set of All Turing Degrees

I ran into a following claims on my complexity notes, that doesn't sense to me: 1) We have a Turing Degree like a, such that for any other Turing Degree like ...
-1
votes
1answer
56 views

Why we cannot infer {$1393$} $ \leq_M \bar {K}$?

We know the halting set $K$ is undecidable. Why we cannot define {$1393$} $ \leq_M \bar {K}$. ...
3
votes
1answer
228 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
105 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 $ ...
-2
votes
1answer
103 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
109 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
72 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
137 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 ...
-4
votes
2answers
112 views

some points on R.E and Oracle of R.E sets? [closed]

I ran into old-multiple choice question with short answer (1). anyone could learn me about the options ? 1) there is a natural number n, such that $n \in K, K=W_n$ 2) relation of G- r.e ...
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
56 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
65 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 ...
0
votes
2answers
42 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
31 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
88 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
104 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
59 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
52 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?
0
votes
1answer
40 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
22 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
31 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 ...