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

Example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive?

Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a ...
1
vote
2answers
52 views

Are all computable numbers constructable after a countable number of steps?

While looking at another question on this site about constructable numbers I started wondering. If you can take a countable number of steps (possibly infinite) can you draw an interval of a length ...
1
vote
1answer
55 views

Is the theory of Algebraically Closed Fields decidable?

It's easy enough to show that the theory of algebraically closed fields of characteristic p is decidable (since its complete). But does it follow from this that the theory of algebraically closed ...
0
votes
2answers
43 views

Formal languages

Let language $L$ be denoted by the regular expression $a^*b^*$ What is wrong with the following “proof” that $L$ is not regular? Assume that $L$ is regular. Then it must be defined by a DFA with k ...
0
votes
2answers
33 views

formal languages and computability concepts

Prove whether or not language $L$ ={$a^pb^q : p ≥ 100$ and $q ≥ 100$ are fixed integer values, and $i ≥ 0$} is regular. I'm not sure how to prove this.
0
votes
1answer
35 views

Formal languages and Computability

Can someone please tell me how would you start proving this? Thanks Prove whether or not language L = {a^(p+qi) : p and q are fixed integer values, and i ≥ 0} is regular.
0
votes
0answers
17 views

Decidability of the theory of ACF [duplicate]

The theory of Algebraically Closed Fields without specifying the characteristic is incomplete. Why is it decidable ?
1
vote
0answers
27 views

Decidability of the set of axioms of Algebraically Closed Fields

The set of axioms of $ACF_p$ is infinite. Why is it decidable? Is there a way to decide given a number whether it is a code of some axiom of $ACF_p$
2
votes
1answer
86 views

Problems understanding proof of s-m-n Theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
1
vote
1answer
23 views

Is there any procedure saying “this function is not obtainable without using recursion at least n times”?

It is known that $sum(x,y)=x+y$ is not obtainable from any compositions of basic functions $z,s,id^n_i$(zero, successor, projections) without using at least one recursion. also, $\times(x,y)=x\cdot y$ ...
0
votes
1answer
21 views

In recursion theory, is $\Sigma_{i=0}^y f(x,i,z)$ primitive recursive?

It is known that given ternary primitive recursive function $f$, the function $g$ defined as $g(x,y,z)=\Sigma_{i=0}^z f(x,y,i)$ is primitive recursive. I wonder if this formulation can be modified; ...
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
32 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
56 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
27 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
84 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
54 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
68 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
23 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
402 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
68 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
44 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
35 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
67 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
46 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
27 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
156 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
44 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 ...
4
votes
0answers
96 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
76 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
399 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 ...