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)

8
votes
2answers
327 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 } ...
0
votes
0answers
12 views

Is there a way to reverse engineer an already large number to make it smaller? [on hold]

Using the Ackermann function for example, it's quite easy to make massive numbers. My question is whether there's an existing algorithm that can take a large number and reverse engineer it to make an ...
1
vote
2answers
42 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
54 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
15 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
27 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
42 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
47 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
25 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
32 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
0answers
25 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
26 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
30 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
30 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
28 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
61 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
29 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 ...
0
votes
1answer
39 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
40 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
25 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
10 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
123 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
0answers
35 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
36 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
48 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
160 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
127 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
52 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 ...
2
votes
1answer
192 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
75 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
99 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 ...
1
vote
1answer
93 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 | ...
2
votes
2answers
120 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
91 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
30 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
61 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
40 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
29 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 ...
3
votes
1answer
38 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 $ ...
5
votes
2answers
57 views

$\alpha$-computable bounded subset of $\alpha$ is in $L_\alpha$

I would like to prove the proposition 1.12b from Chong, Techniques of Admissible Recursion Theory: Let $\alpha$ be an admissible ordinal. A subset $K \subseteq \alpha$ is in $L_\alpha$ ($\alpha$-th ...
1
vote
2answers
37 views

Computable problem

A mathematical problem is computable if there is an algorithm that decides/solves this problem, right? Can you give an example of such a problem?
3
votes
1answer
43 views

If $\Gamma$ is an infinite set of propositional formulas, is the statement: “$\Gamma$ is satisfiable” decidable?

Here, $\Gamma$ is satisfiable means that there exists a truth function $v$ such that $v(\gamma)=$ True for all $\gamma \in \Gamma$. I know that the set of all propositional formulas is countable (our ...
4
votes
1answer
73 views

What does it mean if a free algebra has an unsolvable word problem?

I wonder how hard identity testing (similar to polynomial identity testing) can be for a free algebra. I thought that in a certain sense, the problem should always be semi-decidable, because the free ...
0
votes
1answer
38 views

Recursive Enumeration of Total Recursive Functions vs Partial Recursive Functions

We have: Primitive Recursive $\subseteq$ Total Recursive Functions $\subseteq$ Partial Recursive Functions There are three points that appear at odds with eachother: 1) The primitive recursive ...
1
vote
1answer
24 views

Are Euler Bricks a Recursively Enumerable Set?

An Euler brick satisfies the Diophantine Equations: $a^2+b^2=d^2$ $a^2+c^2=e^2$ $b^2+c^2=f^2$ Where a,b,c,d,e, and f are integers. Has anyone proved the solutions are recursively enumerable? Or ...
2
votes
1answer
94 views

Is there a statement which require an infinite computation to check, independent of whether its true or false?

Let P be the statement that a particular equation has no solution in integers , if P is true it might not have a proof so that to verify it one has to check all the (countable infinite) cases. However ...
2
votes
1answer
130 views

Non-zero solutions of the system

I have concluded to the following results: An homogeneous linear differential equation in the ring $\mathbb{C}[x]$ has a solution if at least one root of the characteristic equation is equal to ...
4
votes
1answer
77 views

Elimination of quantifiers

What does it mean that a theory admits constructive elimination of quantifiers? A theory admits elimination of quantifiers when each formula of the theory is equivalent to a quanifier-free formula, ...
1
vote
1answer
21 views

Deciding set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

Problem: I need to show that the following language is decidable and if not, if $S$ or $\overline{S}$ is partialy decidable language. $S=\{w_e\;|\;|L(M_e)|\leq 10\}$ That is set of all Turing ...
1
vote
2answers
32 views

Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...