Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
1answer
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 ...
1
vote
0answers
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" ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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
0
votes
0answers
10 views

Proof Using Strong Reducibility

I read the following proof so many times and I could not, for the life of me, figure out how the professor went from (1) to (2). I know to prove $\overline{K} \le A$ , where $\overline{K}=\{x:\...
-1
votes
0answers
28 views

Prove that A = {x : φx = λx.42} is not recursive; i.e., x ∈ A is unsolvable/undecidable. [closed]

please help to understand. Here is a similar example: hint: (via S-m-n) that K ≤ A. Definition. (Complete Index Sets) Let C ⊆ P and A = {x : φx ∈ C}. A is thus the set of ALL programs (known by their ...
3
votes
1answer
31 views

Diagonal argument applied to computable numbers

Upon applying the Cantor diagonal argument to the enumerated list of all computable numbers, we produce a number not in it, but seems to be computable too, and that seems paradoxical. For clarity, ...
3
votes
1answer
27 views

Redundant definition of computable function on $[a,b]$ in Pour-El and Richard book?

In Pour-El and Richard Computability in Analysis and Physics page $25,$ they defined computable function on $[a,b]$ as follows: Let $[a,b]$ be such that $a$ and $b$ are computable real numbers. A ...
0
votes
1answer
30 views

Definition of Productive set

I don't understand the definition of Productive Set in the Cutland's Computability book. DEFINITION: A set $A$ is productive if there is a total computable function $g$ such that whenever $W_{x} \...
0
votes
0answers
69 views

Counting the points of intersection

A set of equations is given as follows: $$ x^{\Omega}+y^{\Omega}=1 $$ $$ (1-x)^{\Omega}+y^{\Omega}=1 $$ $$ x^\Omega+(1-y)^\Omega=1 $$ $$ (1-x)^\Omega+(1-y)^\Omega=1. $$ $(\Omega\subset\Bbb Q) =\{...
0
votes
0answers
39 views

Is $\{x_{nk}\}$ defined by $x_{nk} = \frac{k}{k+n+1}$ computable?

Currently I am reading Pour-El and Richard Computability in Analysis and Physics. In Chapater $0$, they give a definition of computable double sequence. Definition: A double sequence will be ...
1
vote
1answer
73 views

Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively?

Question: Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively? The definition of effective convergence that I am using is: There exists a computable function $e:\mathbb{N}\...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
2
votes
1answer
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 ...
15
votes
2answers
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 ...
3
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 \}$ ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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-...
2
votes
1answer
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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
1
vote
1answer
80 views

Show that $x \in W_{x}$ is undecidable

The Cutland's book called Computability has a theorem whose proof i don't understand and i have developed another simpler proof. Could you tell me if this proof is correct? DEFINITION 1: $\phi_{x}, x ...
1
vote
1answer
42 views

Is there a probabilistic Turing machine whose halting probability is non-measurable?

I was wondering if there a probabilistic turing machine whose halting probability is non-measurable? By that, I mean that the probability measure applied to the event "the machine halts" is undefined.
-3
votes
1answer
81 views

Are all non-computable functions from $\mathbb{N}$ to $\mathbb{N}$ denumerable?

In the Cutland book called Computability, there is a very interesting exercise on page 81. Show that the set of all non-computable total functions from $\mathbb{N}$ to $\mathbb{N}$ is not ...
-3
votes
1answer
94 views

Is there a distinction between a “specific” (“nominated”) real number and an “anonymous” real number?

The Axiom of Choice: If $a$ is a class of non-empty sets $x,$ there exists a function $f$ such that $f\left(x\right)\in{x}$ for all $x\in{a}.$ https://mitpress.mit.edu/contributors/h-behnke The ...
0
votes
1answer
57 views

How to show a function is primitive recursive?

Show that the following function is primitive recursive, by giving its name in official notation, with names for functions drawn solely from the initial primitive recursive functions: f (x) = x^2 + 3x ...
1
vote
1answer
60 views

How to prove or disprove that a machine is Turing Complete?

Given a set of operations machine can perform, how to prove or disprove it's Turing Completeness? Is the definition of a set of operations and corresponding state changes is enough or should I add ...
1
vote
4answers
85 views

How do you prove a multivariable function is bijective? And what is its inverse? [closed]

Let $f:\mathbb{N}^2\rightarrow \mathbb{N}$ $$f(m,n) = 2^m(2n+1)-1$$ How do you prove this multivariable function is bijective? And what is its inverse? This question is important for me because it ...
-1
votes
2answers
137 views

Proof of Godel's Incompleteness Theorem based on Recursion Theorem

I'm looking for a proof of Godel's Incompleteness Problems based on the recursion theorem in computability theory. I've skimmed lots of textbooks but I haven't found such proof. Can you name some ...
1
vote
2answers
38 views

Program or computing system [closed]

What programs do you suggest to me such that when introducing a set of numbers, it will answer possible functions that generate them? Different wolfram, neither OEIS. For example, if I input 2, 3, ...
1
vote
2answers
162 views

Well-definedness of uncomputable functions.

I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never ...
2
votes
0answers
47 views

Is classical Euclidean geometry Turing complete?

By "classical Euclidean geometry" I don't mean the study of $\mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $\mathbb R^2$ that ...
3
votes
1answer
60 views

Why is $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ a recursive set?

Let $\mathcal{N}=(\mathbb{N},+,\cdot,0,1)$. I want to show that $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ is a recursive set. Here $\#F$ is the Gödel number of $F$ and ...
1
vote
1answer
51 views

Show that the greatest common divisor $gcd(x,y)$ is primitive recursive.

Let $x,y \geq 2 $. Actually I have to show that $CD(x,y)$ is primitive recursive, where $ C(x,y) = 1$ if $gcd(x,y)=1$, otherwise $CD(x,y) = 0$. But I have showed that it is enough to show that $gcd(x,...
0
votes
1answer
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 ...
7
votes
2answers
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 ...
6
votes
1answer
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 ...
1
vote
2answers
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.
2
votes
2answers
46 views

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 ...
1
vote
0answers
55 views

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

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R i am looking for the simplest solution- using a known languages that do not demand another formal proof.