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
1answer
32 views

Which language is decidable

Just been at the Math-exam. One question I was really unsure about, was this question - so I didn't answer it, as you get minus point if the answer is wrong. Does somebody know, what the right answer ...
0
votes
1answer
31 views

Definition of a recursive ordinal

I'm having trouble understanding the definition of reclusive or computable ordinal - Wikipedia defines it as follows: "...an ordinal $\alpha$ is said to be recursive if there is a recursive well-...
1
vote
1answer
54 views

How is the non-existence of a solution proven?

I've been wondering how an argument that a solution to a particular problem doesn't exist is put together. For instance "Pour-El and Richards found an ordinary differential equation $\phi'(t)=F(t,\...
0
votes
1answer
25 views

Given a formal system show that a variable contains more of one symbol than an initial part of that variable

Given a formal system[of 4 symbols: 0, 1, ( , ) ] with rules: You may write down 0 or 1 at any time. if strings s and t have been written down, you may write down (st). write ⊢s to mean that s can ...
1
vote
0answers
83 views

Intuitonism and metamathematics.

There are various reasons why one would want to reject the law of the excluded middle when doing "normal" mathematics, which I won't get to here, but accepting those, does the same reasoning hold when ...
1
vote
1answer
53 views

Image of a strictly increasing computable function is computable?

I'm trying to show that if $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and strictly increasing, then $f(\mathbb{N})$ (the characteristic function of its image) is computable. My problem is that ...
0
votes
1answer
51 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{...
-2
votes
2answers
39 views

Proove that Unions and intersections of recursively enumerable sets are also recursively enumerable [closed]

How do I prove that Unions and intersections of recursively enumerable sets are also recursively enumerable?
0
votes
1answer
63 views

Showing set is undecidable with Turing Machines

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket ...
0
votes
1answer
89 views

Is the set of languages over an alphabet Σ missing k words from Σ* countable?

My original question is whether $\mathscr{L}$, the set of all languages over an alphabet $Σ$, each of which missing finitely number of words from $Σ$* is countable. I think I can prove the set is ...
0
votes
0answers
22 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : \...
0
votes
0answers
33 views

Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
7
votes
2answers
401 views

Intuitive meaning of the concept “computable”

My question is a follow-up question to this one: How to show that a function is computable? The original question was: Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x)...
1
vote
2answers
67 views

Is there a way to prove that a Turing machine computes the function we designed it to?

Say we design a simple Turing machine that adds two numbers together. Is there any way to formally prove that the machine actually computes the function we 'know' it does? Is there a general method ...
0
votes
1answer
70 views

Is it possible to create a software to find formal proofs?

Let's say I have a Hilbert style system, with a few axioms and rules of inference, and I want to find a proof for some formula $\varphi$, is it possible to create an algorithm that would find a proof ...
1
vote
1answer
38 views

Emptiness and infiniteness decidable for recursive languages?

The problem of determining whether a recursively enumerable language is empty or infinite cannot be solved. The proof goes by reduction to the problem of decidability, which is known to be unfeasible ...
0
votes
1answer
33 views

There are infinitely many recursively enumerable subsets of the natural numbers which are not recursive

How do I prove this claim? I understand that there are countably many recursive as well as recursively enumerable sets, and that the natural numbers have uncountably many subsets.
1
vote
1answer
61 views

Every infinite recursive set has a recursively enumerable subset which is not recursive.

Is the above statement true? If so, how do I go about proving it? Another thing: Given two recursively enumerable sets $Q_1$,$Q_2$, I want to prove that $Q_1\backslash Q_2$ isn't necessarily ...
0
votes
2answers
153 views

(Enumerable) set of natural numbers might not be effectively enumerable

It is well known that a set of natural numbers, although trivially enumerable, might not be effectively enumerable. I am trying to understand this fact intuitively. What is the decisive element in the ...
2
votes
1answer
33 views

Direct constuction of nonlow noncomplete c.e. sets

How can one construct a noncomplete nonlow c.e. set? (Background: I've been trying to construct, as an exercise, a nonlow low$_2$ set, but I do not know what kind of requirement is adequate for ...
2
votes
1answer
38 views

Does the existence of uncomputable functions imply that a theory is incomplete?

For example Kolmogorov complexity is uncomputable and Chaitin used that fact to prove incompleteness. If this is not the case, can you give me a counter example? Set of axioms is countable.
0
votes
1answer
37 views

A subset of $ \mathbb{N}$ is recursively enumerable iff it is the range of some recursive function from $\mathbb{N }$ to $\mathbb{N}$.

I know how to prove the converse of the statement, but given a recursively enumerable set, I don't know how to find such a recursive function. Also, how to prove that the function can be chosen as ...
0
votes
0answers
37 views

all recursive functions are turing computable

I'm studying with the book computability and logic(boolos). In chapter 5, the theorem is proved, indirectly, by showing that (recursive => abacus) & (abacus=> turing). But I want to prove (...
0
votes
0answers
44 views

Strange use of sigma notation in computability

Ok everyone, so I was reading about computability when I came across the following- ''Suppose that $f(x, z)$ is any function; the bounded sum $\sum_{z<y} f(x, z)$ is a function of $x, y$ given by ...
0
votes
0answers
32 views

A. A. Markov's paper on insolubility of the homeorphy problem [duplicate]

I am aware that this has been asked before, but the paper is nowhere to be found online, the provided link in the old thread leads to nowhere, and I'm really at wits end to find this paper, can anyone ...
0
votes
0answers
32 views

recursively enumerable sets closed under concatenation

I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I ...
1
vote
1answer
66 views

Is the definition of recursive function unchanged if we restrict substitution to binary composition?

When defining recursive functions, are the following two statements equivalent?$$f:\mathbb{N}^n\rightarrow\mathbb{N}^m, g:\mathbb{N}^m\rightarrow\mathbb{N}^k \text{ recursive}\implies g\circ f \text{ ...
0
votes
1answer
30 views

Proving that a certain function is not recursive

Consider the set $R_0=\{+,\cdot,I_<\}$, where $I_<$ is the characteristic function of the 2-ary relation $<$, and for every n let $R_{n+1}=\{p^n_1,...,p^n_n\}\cup R_n\cup C_n$, where $p^n_k:\...
0
votes
1answer
50 views

Counterexample for the reverse implication of Rice's theorem

Here is the version of Rice's theorem I use: Rice's first Theorem: For every non-trivial, language invariant property $P$ of a set of Turing machines it holds that the set $$\{M | P(M) \}$$ is ...
1
vote
3answers
46 views

Disprove bijection between reals and naturals

Coming across diagonalization, I was thinking of other methods to disprove the existence of a bijection between reals and naturals. Can any method that shows that a completely new number is created ...
1
vote
1answer
26 views

Shifting bounded quantifiers

The universe of the following variables are the natural numbers $\mathbb{N}$. I found in the literature the following logic equivalence: $\forall n < k \exists m \ \varphi(m,n) \leftrightarrow \...
0
votes
1answer
13 views

Substituting functions into other functions in computability, need help with Cutland

I'm working my way through the Cutland text on computability and I'm having a little trouble understanding exactly what he's saying in regards to substituting functions into other functions (if you ...
5
votes
3answers
155 views

Fast-growing noncomputable functions

A famous 1962 paper by Tibor Radó shows that the "busy beaver" function $h$ (which computes the maximal number of steps for which a halting Turing machine with $n$ states can run for) satisfies the ...
0
votes
1answer
43 views

Dominating function easier to understand

Is there a pair of function $f$ and $g$ (both $\mathbb{N}\rightarrow\mathbb{N}$ and definable in the language of first-order Peano arithmetic) such that asymptotically $f$ dominates $g$, and $f$ has ...
2
votes
0answers
50 views

How are weakly universal Turing machines actually defined?

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source): A Turing machine $M$ is called ...
0
votes
1answer
73 views

Recursively enumerable sets as image of a function

I want to show the following claim: An infinite recursively enumerable subset of the natural numbers is the image of an injective recursive function. What I know is that given a r.e. set $A\subset \...
0
votes
1answer
398 views

A function f(n) satisfies the recurrence f(n)=4f(n/2)+n for real numbers. Give an upper bound for f(n)?

A function f(n) satisfies the recurrence f(n)=4*f(n/2)+n for real numbers. Give an upper bound for f(n)? I get somewhere T(n) = Θ(n^2), is that correct?
3
votes
2answers
170 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
2
votes
1answer
67 views

Using Rice's theorem to prove undecidability of $A_{TM}$

Can you use Rice's theorem to prove that the acceptance problem is undecidable? Wikipedia says that it can be used to solve the Halting problem too but I can't see how that works either. Here is the ...
3
votes
1answer
231 views

How to show that a function is computable?

Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable? Please note that $\phi_i(x) \...
3
votes
1answer
81 views

Definable non-computable number which contain no information

We have three types of numbers AFAIK: a) Computable b) Definable and non-computable, but contains information about Halting of some turing machines, extractable in a computable way if you were given ...
0
votes
1answer
108 views

How to find an index of a computable function?

Is there an index $i$ such that $\phi_{p(i)}(0) = i + 2$, for a total computable function $p$? I know about the s-m-n theorem and fixed point theorem, and how to apply them to some basic functions ...
1
vote
1answer
113 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | \text{Dom}(\phi_i)...
2
votes
2answers
138 views

How to define $f(x) = 2x$ as a recursive and lamba function?

How can I exhibit a recursive function and a $\lambda$-term simulating the function $f : \mathbb{N} \rightarrow \mathbb{N}$, such that $f(x) = 2x$? For $\lambda$ part, I thought to create a mult ...
1
vote
1answer
96 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
4
votes
1answer
38 views

Weak and strong computability of real numbers

Let me adopt the following definitions: A real number $x$ is weakly computable if it satisfies one of equivalent definitions given here. A real number $x$ is strongly computable if the binary ...
0
votes
1answer
77 views

Prove that this function is primitive recursive?

Let $g : \mathbb{N} \rightarrow \mathbb{N}$, $n\mapsto$ the $(n+1)^{th}$ natural number which is not prime. I have to prove that $g$ is a primitive recursive function. My attempt is by minimization :...
0
votes
1answer
51 views

Is Soare still the go-to comprehensive guide of computability, or should I use a different textbook?

So, I was looking up some old threads, and I saw Robert Soare's Recursively Enumerable Sets and Degrees get a lot of Praise. However, I also saw the following textbooks be praised quite a bit: ...
1
vote
0answers
34 views

Undecidability and the representation theory of $K<X,Y>$

The question comes from the problem here: http://mathoverflow.net/questions/73940/are-wild-problems-related-to-undecidable-ones It has already been proven that the representation theory of $K<X,Y&...
3
votes
1answer
43 views

Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3 $ ...