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

Filter by
Sorted by
Tagged with
1
vote
0answers
32 views

Necessity of decidable type checking for formalizing mathematics

If a type theory such as Martin-Löf's dependent type theory (MLTT) is to be used as a foundation for mathematics, decidable type checking is certainly nice to have: it guarantees that for every proof ...
-1
votes
2answers
41 views

The set of elements that are members of this set?

Can a set refer to itself in its own definition / define itself in the above way? Is the above set a set? variant: A word w is a member of a language L iff it is a member of language L, ie. the ...
0
votes
0answers
14 views

Turing Equivalence counterexample

Given that A is Turing reducible to B, what would the set B need to look like such that B is not Turing reducible to A? I've been having a hard time with this idea and I would appreciate some examples ...
2
votes
0answers
47 views

Does the existence of Gödel universal functions make the S-m-n theorem unnecessary?

The problem of deciding, for any $x$, whether $\phi_x$ is a constant function, is undecidable. I came across the following proof of this fact in Rogers' book: To me, it looks too bulky and ...
1
vote
0answers
22 views

Where to find/what is full μ-expression for Ackermann function?

Can you point me to full description of the Ackermann function in terms of standard μ-opertor and primitive recursion? I understand that to define it completely down to primitive terms (numerals, ...
1
vote
0answers
29 views

On the proof of the unsolvability of the word problem in semigroups

I'm trying to understand the following proof of the unsolvability of the word problem in semigroups. I tried to reproduce the proof from some kind of personal communication, so I'm not sure everything ...
4
votes
1answer
105 views

Any advantages of using Gödel universal functions in proving unsolvability?

Let $U$ be a universal function for the class of computable functions of one variable. This means that $U:N\times N\to N$ is a computable (partial) function and for every computable (partial) function ...
5
votes
1answer
47 views

Question about unclear definition of Ackermann-Péter function in Stanford Encyclopedia of Philosophy

I'm reading Recursive Functions at Stanford Encyclopedia of Philosophy (section 1.4). The following paragraph defines function β which is then used to define variant of Ackermann-Péter function: What ...
2
votes
0answers
25 views

Mealy-Moore machine book recommendation

I've been researching Mealy and Moore machines for quite some time but it seems to me like there is a lack of good books/articles on the topic. All the research in this area seems to be mainly focused ...
1
vote
1answer
50 views

Will this function grow faster than Busy Beavers as $n \to \infty$

Consider the following function: $$f(x)=x \uparrow ^{x} x$$ Where the notation $\uparrow$ is Knuth's up-arrow notation and $\uparrow ^{n}$ means $n$ number of up-arrows. For example, $2\uparrow ^{4}...
1
vote
1answer
62 views

The halting problem at zero

Consider the set $\{p:U(p,0)\text{ is defined}\}$ where $U$ is a universal function. I'm trying to understand the following sketch of proof of the fact that this set is not solvable. The first claim ...
1
vote
1answer
75 views

Confusion about definitions of a universal function

I've seen these two definitions of a universal partial function for partial computable functions of one variable: It is a (partial computable, I suppose, though it does not appear in the source) ...
1
vote
0answers
24 views

Creative sets (Jockush-Mohrherr)

Recently I have found statement that claims: (Jockusch-Mohrherr) Let A be any c.e. set except ω. Then A is creative iff (∀c.e.B) [A∩B=∅ ⇒ A ≡ A∪B]. But I couldn't find any proof of it. Can somebody ...
0
votes
1answer
40 views

Does the definite description operator generate all general recursive functions?

Suppose, instead of adding the $\mu$ operator to the primitive recursive functions, we add the definite description operator. For a given relation $R$, the definite description operator returns the ...
0
votes
1answer
37 views

Show that maximal set is not recursive

Define set $M$ such that its complement is infinite and for any computable set the intersection $M^C\cap R$ and $M^C\cap R^C$ are not both infinite. How to show that $M$ is NOT recursive, given we ...
0
votes
1answer
41 views

Relative completeness of first order arithmetic

Gödel's incompleteness theorem tells us that the language of first order arithmetic $PA_1$ is strong enough to express a statement about its own consistency, which cannot be proved in $PA_1$. More ...
1
vote
1answer
35 views

Difference between Shannon Entropy limit and Kolmogorov Complexity?

I've read in numerous places that Shannon Entropy provides some kind of fundamental limit to the compressibility of messages (according to, for example, Shannon's source coding theorem). I have also ...
0
votes
1answer
64 views

Existence of infinite sets of a certain property

I've been thinking about this problem for a long time, but I can't come up with a solution. It must be proved that there exists an infinite family of infinite pairwise disjoint subsets of $\mathbb{N}$,...
0
votes
1answer
34 views

When formulating general recursive functions, did Godel knew that they correspond to effectively calculable functions?

...or did it only became apparent after Church's thesis (which asserted that lambda-definable functions and recursive functions are equivalent) and subsequent Turing's thesis? It is known that Godel ...
0
votes
0answers
63 views

The family $\text{CF} \cup \left\lbrace \omega \right\rbrace$ is not computable.

I've got an interesting task from my friend and didn't understand, how to prove that: The family $\text{CF} \cup \left\lbrace \omega \right\rbrace$ is not computable. $\text{CF}$ is the family of ...
0
votes
2answers
20 views

How to write a program from a predecessor function using only the clear, successor, copy, for loop and while loop commands?

This is a question from the first chapter of Herbert Endertons Computability book I've been stuck on it since yesterday and its been driving me crazy. The basic commands from this language are as ...
0
votes
0answers
59 views

Indexed family of all unary partial computable functions. The existence of computable numbering

Please help prove the following statement: The indexed family of all unary partial computable functions that have total computable extension is computable. Definitions: Total function - a ...
0
votes
0answers
23 views

Computable Real Equality

Equality of computable reals is not itself computable. I'm interested in settings where it is computable. Trivially, we can make it computable by shrinking our set of reals to the rationals. Is ...
0
votes
0answers
21 views

Is a halting problem oracle to itself possible if randomness exist?

The usual proof that a halting problem oracle to itself don't exist is like: Check if itself halt, and do the opposite. Both result are conflict. However, if it sometimes return HALT while ...
0
votes
1answer
36 views

Defining Partial Recursive Functions with their indices

I am working on learning recursion theory and I would like to know if there is any danger in defining a partial recursive function that uses its own enumeration. For example: $h(x) = \begin{cases}...
1
vote
1answer
21 views

Is the halting problem an example of a paradox that arises under vary specific conditions (like a division by zero,) or is it more general than that?

If I were to attempt to make a computer program that resolves whether a program defined by a given base of code will halt or not, would the contradiction described by the halting problem arise as a ...
1
vote
1answer
29 views

Prove that two sets recursively inseparable.

Let φ be the standard indexing of the partial computable functions. Prove that the sets $$A = \left\{e : φ_e(0) = 0\right\}$$ and $$B = \left\{e : φ_e(0) = 1\right\}$$ are recursively inseparable In ...
2
votes
1answer
28 views

Recursive set that many-to-one reduces to a non recursive set

It is a known theorem that if B is a recursive set and A many-to-one reduces to B, then A is also a recursive set. I am looking for a counterexample for the converse, so a non-recursive set B such ...
0
votes
1answer
29 views

Is this a proper recursive ordinal notation for ordinals < $\omega^2$?

After making another question about ordinal notation I want to clear some confusion I have about the topic. Let consider ordinals less than $\omega^2$ (or in $\omega^2$) , any of such ordinals can be ...
0
votes
0answers
37 views

Turing degrees of subsets of Kleene $\mathcal{O}$ which are ordinal notations of subsets of the set of recursive ordinals

An ordinal $\alpha$ is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type $\alpha$. The smallest ordinal that is not recursive is ...
0
votes
2answers
56 views

Difficulty with definition of function

My question concerns a definition of an evaluation function with respect to some assignment between the variable set (which let us say is just $V = \{x_1,x_2,...\}$) of some specified first order ...
6
votes
1answer
84 views

What does “forcing an open set” mean?

The set-theoretical notion of forcing is based on a poset $\mathbb{P}$ (the forcing notion) that allows us to define suitable names of elements we want to appear in the forcing extension of our ground ...
0
votes
0answers
97 views

Is it true that computability = constructivism + law of excluded middle?

It seems to me that (classical) computable mathematics and constructive mathematics follow roughly the same program, i.e. only working with objects which can explicitly be constructed (by an algorithm,...
2
votes
2answers
66 views

Can the computability of a specific function be independent of ZFC?

If I understand correctly there exist artificial examples. Let P be a statement known to be independent of ZFC, such as CH, $g:\mathbb{N}\rightarrow\mathbb{N}$ be a function known to be uncomputable, ...
0
votes
1answer
23 views

How to do the integral part of logarthm with minimizer?

I have this function: $r: N -> N $ $r(n) = \log_2(n)$ I have arrived at a version with maximization: $r(n) = max(t) : n >= 2^t$ How do I rewrite it as a recursive function using a bounded ...
1
vote
1answer
54 views

Is Halting problem an example of a problem which is true but unprovable?

I have a difficulty understanding Gödel's incompleteness theorems. If it is proven semantically that some problem is undecidable (such as Halting problem), does it means that such a statement is "true ...
0
votes
1answer
21 views

Show that the index set of this set of partial computable functions is not computably enumerable

Assume $\mathcal{K}$ is the set of all partial computable functions $f: \omega \rightarrow \omega$ such that $\vert \{x:f(x)=0\}\vert \leq 2$. I want to prove that the index set $I=\{k\in\omega:\...
6
votes
0answers
81 views

Does having many models yield complex second-order theories?

Below, $T$ is a complete first-order theory in a finite language with no finite models. Question Suppose $T$ has continuum-many countable models. We define two sets of Turing degrees associated to $...
2
votes
1answer
32 views

Prove that $A^{(\omega)}\nleq_T A^{(n)}$

I am trying to solve Exercise 7.1.24 (i) of Computability Theory by Rebecca Weber. $A^{(n)}$ denotes the $n$-th Turing jump and $A^{(\omega)}=\{\langle x,n\rangle: x\in A^{(n)}\}$ the $\omega$-jump. ...
2
votes
1answer
52 views

$A$ are the even numbers, is there a non-computable set $B$ such that $A\nleq_1 B$?

Assume $A,B\subseteq \omega$, we say $A\leq_1 B$ (1-reducible) if there is a injective computable function $f$ such that, for all $x$, $$x\in A \Leftrightarrow f(x)\in B.$$ Now assume $A$ are the ...
1
vote
2answers
40 views

How does this integer division work?

In "Theory of Computation: Formal Languages, Automata, and Complexity" Spanish ed. (p.220) it says that: $$ div(x, y) = μt[((x + 1) \dot{-} (mult(t, y) + y)) = 0] $$ Where $mult$ is the integer ...
0
votes
1answer
21 views

Clarification on Defining Partial Recursive Functions

I've been working on learning about recursion theory, and I've been doing problems with partial recursive functions. I stopped myself when I wrote something like this: Let $g: \mathbb{N} \...
0
votes
1answer
13 views

The class of primitive recursive functions

Usually the scheme of primitive recursion is defined as follows: $$ h(x, 0)=f(x) \\ h(x, y+1)=g(x,y,h(x,y)) $$ I was wondering whether the class of primitive recursive functions would be smaller if we ...
1
vote
0answers
45 views

Can we tell if a given rational point is a point on the Sierpiński triangle?

Stated precisely, is the indicator function for the Sierpiński triangle restricted to rational points in the plane a computable function? My intuition is telling me no, but maybe the fractal folks ...
0
votes
1answer
29 views

Is signum a computable function?

Let $\mathbb{M}$ be the set of real computable numbers, and let $\text{abs, signum} : \mathbb{M} → \mathbb{M}$. They are defined as: $$ \text{abs}(x) = \text{if} \quad x ≥ 0 \quad \text{then} \quad x \...
0
votes
1answer
40 views

How to prove the diagonal Lemma

I am interested in understanding the proof of Gödel’s Incompleteness theorems. The diagonal Lemma is used to prove the existence of self-referential statements. But as I read the proof of the Diagonal ...
-1
votes
1answer
46 views

Why are constructible numbers strict proper subsets of computable numbers? [closed]

Well, obviously $\pi$ is transcendental, therefore not in the algebraics. Constructibles are clearly a subset of the algebraics so $\pi$ is not constructible. Yet $\pi$ is computable. Thats a perfect ...
0
votes
1answer
53 views

How exactly do diophantine polynomial equations map to turing machines?

From a wikipedia page: One can write down a concrete polynomial p ∈ Z[x1, ..., x9] such that the statement "there are integers m1, ..., m9 with p(m1, ..., m9) = 0" can neither be proven nor ...
3
votes
2answers
75 views

Computational complexity of real numbers

Recently, I've been studying computable analysis. One of the basic notions is a computable real number, which I will define as any $r \in \mathbb{R}$ which has a computable Cauchy name - a computable, ...
3
votes
1answer
60 views

Equivalent definitions of $\omega_1^{\mathrm{CK}}$

This is perhaps a somewhat tedious and technical question, but I've seen two definitions of $\omega_1^{\mathrm{CK}}$ (one from order-types and one from Kleene's $\mathcal{O}$), and I'm not immediately ...

1
2 3 4 5
37