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)

0
votes
0answers
33 views

Church’s Thesis with regard to R-decidability and R-enumerability.

Church’s Thesis with regard to R-decidability and R-enumerability: If some set is enumerable/decidable, then there exists a program, i.e., a register machine, with respect to which the set is ...
1
vote
0answers
52 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
3
votes
2answers
39 views

Decidability of predicate calculus with equality only

I read in some books that propositional calculus is decidable (e.g. with truth tables), and predicate calculus is not decidable (as proved by Church and Turing). Unfortunately, I do not exactly ...
1
vote
1answer
52 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
4
votes
2answers
63 views

Can you solve the halting problem for a single, non-universal Turing machine?

So, I'm familiar with the halting problem and its proof. However, I also understand that the proof is for any universal machine $U$; that is, the set ...
1
vote
0answers
32 views

Are all finite languages regular?

I've been thinking about this for a while and still cannot come up with a way to show that all finite languages are regular. I know that all finite languages consist of finite number of strings that ...
2
votes
0answers
33 views

Is there any research on Diophantine Approximation with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
0
votes
1answer
53 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
6
votes
4answers
108 views

Is the logarithm of $\aleph_0$ infinite?

In classical mathematics $2^{\aleph_0}=\aleph_1$, right? So if $2^x=\aleph_0$, what does $x$ equal? In other words, can we define a logarithm for $\aleph_0$, and what should it be. Is it infinite? ...
0
votes
0answers
12 views

Approximation of set cover with randomized algorithms

I know that it is np hard to approximate set cover with a factor o(log(n)). Is there a similar result of hardness to approximate using a ranomized algorithm? Is there any article about that?
2
votes
0answers
57 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
21
votes
7answers
2k views

Example of uncomputable but definable number

Every computable number is definable. However, the converse is not true. What is an example of a real number that is definable but that is NOT computable? I guess if it is there, we can "define" ...
2
votes
2answers
104 views

How to understand this informal description of the levels of the arithmetical hierarchy?

In my class notes I do not understand why the following statement is true, nor what it means: Informally, the lowest level in the Arithmetical Hierarchy in which $n$-ary relation $R$ is definable ...
0
votes
2answers
31 views

Examples of undecidable languages contained in 1*?

I've been given the following question Show that there is an undecidable language contained in $1^*$. But I can't think of any undecidable languages that are contained! Can someone please lend a ...
1
vote
1answer
47 views

Proof that mappings $K$ and $L$ are primitive recursive.

Let $J$ be the function: \begin{equation*} J(m,n)= \begin{cases} n^2+m \text { if } m\le n \\ m^2 + m + (m-n) \text { if } m > n \\ \end{cases} \end{equation*} Let $K, L$ such that $K(k)$ is ...
0
votes
3answers
76 views

Can we simplify analysis by getting rid of the uncountable reals? [duplicate]

Since the entire observable part of the universe can only be in a finite number of physically distinguishable states, it seems rather strange that an efficient formal description of the universe would ...
5
votes
0answers
128 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
2
votes
1answer
49 views

Proving the principle of definition by generalized recursion using the inductive closure of an induction system

I'm working through Hinman's Fundamentals of Mathematical Logic in order to review some things, and got stuck in an exercise from section 1.2. Specifically, he asks us to prove (what he calls) the ...
0
votes
0answers
130 views

Decidability of determining the definition of a function

Let's say a property is an SMT formula. Let's say a function has a property iff, with addition of the function symbol to a monadic predicate calculus formula over the signature of Presburger ...
3
votes
2answers
66 views

What's the significance of the Church-Turing Thesis?

My understanding is that the thesis is essentially a definition of the term "computable" to mean something that is computable on a Turing Machine. Is this really all there is to it? If so, what makes ...
2
votes
1answer
74 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
50 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 ...
5
votes
1answer
86 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
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 ...
1
vote
2answers
97 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
94 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
25 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
29 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
66 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
88 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
51 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
69 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
105 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
44 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
62 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
188 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
72 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
60 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
46 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
237 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
121 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
88 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
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 ...