# Tagged Questions

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).

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 ...
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 ...
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 ...
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 ...
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.
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.
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 ?
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$
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 ...
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$ ...
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; ...
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 ...
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-...
56 views

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?
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 ...
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 ...
23 views

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 ...
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 ...
27 views

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?
### 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?