# Questions tagged [computability]

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

1,610 questions
19 views

### Compute a series from a sequence

Let's say I have a sequence $s_n$ of numbers, and I want a series $a_i$ which computes the sequence; that is $\sum_{i=0}^\infty a_i n^i = s_n$ Clearly $a_0 = s_0$, but after that I am stuck. I need ...
21 views

### Make the language of First Order Logic uncountable

The question is in regards to The Lowenheim-Skolem theorem and the question asks to give a set of sentences that is only true in an uncountable domain. My teacher told me to solve this by "relaxing" ...
20 views

### is there a linear bounded automaton the decides $A_{nfa}$?

first post here :) I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
25 views

### Is every degree above ${\bf 0''}$ PA over something close to itself?

The low basis theorem says that there are PA degrees which are low - that is, which satisfy ${\bf a'}={\bf 0'}$. Appropriately relativized, given a degree ${\bf a}$ there is a degree ${\bf b}$ "not ...
70 views

### What does this notation mean? $\Phi(x) \downarrow, \Phi(x) \uparrow$

I'm not sure how I am supposed to know this, I have never used notation like this in my previous school. Is this notation logic or is it something I should have learned in math class? What I am ...
41 views

### What is a “n-valued function”?

Has $n$ parameters? i.e. 0-valued function: $f(\emptyset)=2$ 1-valued function: $f(x)=x$ 2-valued function: $f(x,y)=x+y$ 3-valued function: $f(x,y,z)=x+y+z$ Not sure
10 views

69 views

20 views

### A question about the non-transitivity of $\leq_{w\alpha}$

A very natural question when reading about $\alpha$-recursion theory is why and when the weak $\alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The ...
10 views

### How to show directly that Fin = $\{e \colon W_e\textrm{ is finite}\}$ is not c.e.?

How can I show directly that Fin = $\{e \colon W_e \textrm{ is finite}\}$ is not a computably enumerable set? I have been trying to do this directly without alluding to the arithmetical hierarchy and ...
46 views

### Is the finite set of all partial functions in $\mathbb{N}$, $f:(0,n)\rightarrow (0,n)$, computable?

I have developed the next conjecture: CONJECTURE: The set of all partial functions in $\mathbb{N}$, $f:(0,n)\rightarrow (0,n)$, being n a finite natural number, is a set of computable functions, ...
50 views

### Complexity of a recursive algorithm on formulas of propositional logic

A proof I've seen on reductions for $\mathsf{NP}$-hard problems relies on evaluating the complexity of an algorithm computing a function which is defined recursively in the structure of formulas of ...
54 views

### Arithmetical Hierarchy - Classification of sets

I am currently working on a problem to classify the following set: $A = \{e \mid W_e \subset \{0,1\}\}$, where $W_e$ is the domain of some recursive function with code $e$. I originally formulated ...
92 views

### Cofinality of $\omega^{CK}_{\omega_1+1}$

What is the cofinality of this ordinal (say in ZFC)? Is it countable or not? Edit: Based on reason for close, I have added some informal motivation for question. Based on the computability-theoretic ...
742 views

### Is the theory of the category of topological spaces computable?

This question is inspired by this Mathoverflow question. Ignoring size issues, there is a natural way to view a category as a first-order structure in a finite language. In light of this we can ask ...
40 views

### A continuum-sized convenient category of topological spaces

From the concluding section of Quasi-Polish Spaces by Matthew de Brecht: "It turns out that the category of quasi-Polish spaces and continuous functions has a very natural description: up to ...
49 views

### Can we see all mathematical concepts as (possibly uncountable-time) algorithms?

Note: I am interpreting “algorithms” broadly, to include algorithms that require an infinite and even uncountable number of computational steps. It seems to me that any definition can be seen as a ...
26 views

### What does it mean for a set $A$ to be computably enumerable in another set $B$?

In my introductory computability class I keep seeing the phrase set $A$ computably enumerable IN set $B$? I don't want a definition of computably enumerable, I know what that is, and there are a lot ...
20 views

### L = {$(n,w)$ $w$ is a binary representation of the n-th fibbonacci number} membership decision problem

I am a student currently studying Computational Models. I still don't have a full understanding of the subject and was wondering about languages of the form $L = \left \{(n,w) | f(n) = w \right \}$ ...
46 views

### Examples of computable sequence of rational numbers

I am a beginner to computability theory and curently reading Pour-El and Richard Computability in Analysis and Physics, Chapter $0$. At page $14,$ they provided a definition for computable sequence ...
32 views

### Partially Non-Computable Numbers

Could there be a number say: A = $0.a_1a_2\cdots a_n$->$a_k \cdots$ where say {$a_1a_2$} and {$a_n$->$a_k$} are computable parts of A. Yet every thing else is not computational. I imagine a scheme ...
24 views

### Real number pattern (non-computable numbers)

supposedly the real numbers have a pattern like: [ABABA] where A represents rational numbers and B is irrationals s.t. $A0<B0<A1<B1<A2$. Is there a similar pattern which includes non-...
54 views

### How can you construct the bijection between real numbers and functions over naturals? [duplicate]

I was reading "Classical Recursion Theory" by Odifreddi and it starts with this phrase: Recall that Classical Recursion Theory is the study of real numbers or, equivalently, functions over the ...
14 views

### Turing Machines recognizing the same language

Is it possible for two turing machines that take different types of inputs, for example $\langle M,w\rangle$ and $\langle M\rangle$, to recognize the same language?
9 views

### projection functions class closed by primitive recursion and composition?

I've stumbled upon the following exercise and I am having some doubts with the solution: Let $\mathcal{C}=\{{u_i}^n:1\leq i \leq n\}$ be the class of all the projection functions. Decide if the ...
80 views

49 views

### Is this proof Ok? ( about computing languages with no loops)

I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter. What's wrong with the following argument: If there's an ...
61 views

### Is it possible to put a topology on Turing-recognizable languages to express density among all the languages?

In a Calculability and complexity course I had at univeristy, we proved that there exist languages that are not Turing-recognizable basiclly using Cantor's diagonal argument (the set of all languages ...
93 views

### What is the Turing degree of Truth?

First of all by Truth I mean the set $T$ of the Gôdel numbers of the true formulas of first order arithmetic. First order arithmetic is not decidable and $T$ is not decidable, additionally the ...
37 views

### Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]

"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
### Simple example of the minimization operator $\mu i$?
This is the definition of a minimization operator from A friendly Introduction to Mathematical Logic. I'm having trouble understanding this. How can this map a function of $n+1$ variables to a ...