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).
2,339
questions
0
votes
0
answers
30
views
How to define multivariable double recursive function
I have a question for those who are familiar with recursion theory.
According to Wikipedia (https://en.wikipedia.org/wiki/Double_recursion),
Raphael M. Robinson called functions of two natural number ...
-1
votes
0
answers
28
views
Definition of multiple recursive functions [closed]
According to Wikipedia, functions of two natural number variables $G(n, x)$ is double recursive with respect to given functions, if
$G(0, x)$ is a given function of $x$.
$G(n + 1, 0)$ is obtained by ...
0
votes
0
answers
142
views
Can a decider return "Undecidable" on the Halting Problem?
So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output {0 if doesn't halt, 1 if halts, U if ...
3
votes
1
answer
52
views
Reverse mathematics of characterization of compact spaces
It is known that, over $\text{RCA}_0$, the Heine-Borel theorem is equivalent to $\text{WKL}_0$ and that the Bolzano-Weierstrass theorem is equivalent to $\text{ACA}_0$.
In general, a topological space ...
- 747
0
votes
1
answer
54
views
Difference definable vs. computable
Is it true that a computable number or function is always definable, while the other way around is not?
It seems so based on the following link: just want to confirm
https://math.stackexchange.com/...
- 33
1
vote
1
answer
61
views
Why doesn't Cohen's definition for the $\mu$ operator result in non-computable functions?
I am reading Paul Cohen's Set Theory and the Continuum Hypothesis. Cohen defines the $\mu$ operator as{}^1
$\mu_y f(y,x_1,...,x_n) \equiv g$
where
i) $g(x_1,...,x_n) \equiv 0 \text{ if for any } \...
- 703
1
vote
0
answers
55
views
Decidable formal language with a finite but non-computable size
I'm looking for a formal language that has the following properties:
Contains finitely many words (and you can prove it).
Decidable/recursive (there's a Turing machine that always halts, that can ...
- 113
0
votes
0
answers
19
views
Proving the Computability of the Function $\beta$ Analogous to Another Function
I am studying a Theory of Computability.
Before the theorem I should provide you with the definition of limited sum and product, respectfully:
$\alpha(x,y)=\sum_{z<y}f(x,z)$ which is defined with ...
- 43
7
votes
2
answers
142
views
Does this paradox prove that the halting problem is undecidable?
A real number is said to be computable if a finite, terminating algorithm can compute it to arbitrary precision. Since algorithms are countable (for example, one may list all possible c programs in ...
- 73
3
votes
0
answers
57
views
Probabilistic Kleene's recursión theorem
Kleene's recursion theorem states that for every total computable function $f$ there is an index $e$ such that $$\phi_{f(e)} = \phi_e,$$ where $\phi_n$ is a valid enumeration of the partial computable ...
- 343
1
vote
1
answer
95
views
About Gödel's completeness and incompleteness theorems
I am using ZFC as a tool to demonstrate my problematic logic.
In zfc we construct a proof system for zfc in zfc (a simulation of a proof is what I mean); we will call it inner proof system. We ...
- 13
0
votes
1
answer
37
views
Equivalence result for Recursion Theorem
A corollary for the Recursion Theorem (Kleene) stands that for every recursive function $f$ there exists $n$ such that $W_{n} = W_{f(n)}$. That result is equivalent to the following one: for every r.e....
- 13
1
vote
0
answers
41
views
Given a recursive function, show there is a n such that Wn is recursive
Let $f$ be a recursive function. Show that there is an $n$ such that: $W_{n}$ is recursive; and $(\mu y)[ W_{y} = \overline{W_{n}} ] > f(n)$. Hint: Enumerate a finite set $W_{n}$ by first computing ...
- 13
1
vote
0
answers
40
views
Formalizing modus ponens on $PA$ arithmetic theory.
In the (short) book
[J] "Notes on logic and set theory" (Peter Johnstone).
The author P.J. considered the first order Peano language of naturals (the $\bar{0}$, the successor $S$, $+$, $\...
- 426
0
votes
0
answers
23
views
Equivalence result on recursive enumerable sets
I am reading the book of Robert Soare for recursive enumerable sets and degrees. There is the so called listing theorem, which stands that a set A is recursive enumerable if and only if A is not empty ...
- 13
0
votes
1
answer
70
views
Proof for halting problem is recursively enumerable
So, I know the proof for Halting Problem is not recursive using diagonalization. We prove it using proof by contradiction. First we assume HP is recursive which implies there is a Total Turing Machine....
- 3
1
vote
0
answers
60
views
Could analog computers be used to solve a set of PDEs w/o the traditional numerical instability problems that come from discretizing the domain?
The question is simple. Could analog computers (for example, electrical analog computers) in effect avoid traditional numerical instability problems that come from solving a set of PDEs over a ...
11
votes
1
answer
430
views
Why is incomputability weaker than Kolmogorov complexity?
Abbot et al. "Experimentally probing the algorithmic randomness and incomputability of quantum randomness" remark that "incomputability is a weaker property than Kolmogorov randomness&...
- 1,328
2
votes
0
answers
57
views
Proving $\omega_1$ is measurable from Martin Measure being an ultrafilter
AD implies that each set of Turing degrees either contains a cone or is disjoint from one. It follows that the set of Turing degrees has a countably additive measure: $\mu(A) = 1$ if $A$ contains a ...
2
votes
0
answers
81
views
Is the function sending a sentence to the diagonal of a sentence form extended over it, computable?
Is, the following function $h$ computable?
Let $h: \mathbb N \to \mathbb N $ be the function defined by:$$h(\ulcorner s \urcorner) = \ulcorner D(E_s(v)) \urcorner$$
for each sentence $s$ in the ...
- 4,417
0
votes
1
answer
28
views
Is $f$ primitive recursive in $g$ if $f$ does not eventually dominate $g$?
Let $f:\mathbb{N} \to\mathbb{N}$ be a monotonous numbertheoretic function, and let $g:\mathbb{N} \to\mathbb{N}$ be such that
$$\forall m \exists n f(n)\leq g(n).$$
Is $f$ always primitive recursive in ...
- 650
1
vote
1
answer
51
views
Proof: Busy Beaver function is not calculable
I'm studying in a textbook and one exercise was to proof that the busy beaver function $B(n)$ is not calculable. My solution differed quite a bit from the one given in the textbook, so I wanted to see ...
- 13
0
votes
0
answers
105
views
Does Curry-Howard correspondence mean that everyone who writes a program is doing intuitionistic mathematics?
As far as I know, the first statement of the correspondence is between two formal theories named simply typed lambda calculus and intuitionistic propositional logic, which maps types to formulas and ...
- 23
1
vote
0
answers
41
views
Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof
all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?
TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
- 145
0
votes
0
answers
32
views
Trying to understand the idea behind this reduction
I'm currently learning about polynomial reductions in my computational models course, and there's this reduction which I cant wrap my head around:
We're given the language $ L=\{{<M,w> | w\circ ...
- 389
1
vote
0
answers
21
views
Are functions under which preimage of recursive sets are recursive sets always recursive? [duplicate]
It is well known that preimage of a recursive set under a recursive function is a recursive set (see for example Image and preimage of a recursive function on a recursive set).
I wonder whether some ...
- 11
-1
votes
1
answer
48
views
non primitive recursive algorithms having polynomial time verification? [closed]
i think the title speaks for itself,
since the defining trait for NP class is that - they are the set of decision problems verifiable in polynomial time by a deterministic Turing machine.
thus it ...
user1203789
1
vote
0
answers
87
views
Let $\pi$ be a $ℍ𝑌𝑃_𝔐$-recursive projection of $ℍ𝑌𝑃_𝔐$ into 𝔐. What does $ℍ𝑌𝑃_{(𝔐, Domain(\pi))}$ contain?
Let $\pi$ be a $ℍ𝑌𝑃_𝔐$-recursive projection of $ℍ𝑌𝑃_𝔐$ into 𝔐 (we know it exists by the classic results of Barwise in Admissible Sets and Structures (II.5.14, V.5.3, and VI.4.11/12)). The ...
- 11
4
votes
1
answer
82
views
Representability of Goodstein function in PA
I have a doubt concerning the representability of Goodstein's function in Peano Arithmetic ($PA$). Specifically, the function
$G(n) =$ “The length of the Goodstein sequence starting from $n$”
is ...
- 343
4
votes
1
answer
63
views
How do proofs of program termination depend on strength of logical systems?
I'm looking for clarifying insights on the following topic. While there can be no general proof strategy to show that terminating Turing programs do, indeed, terminate, some specific programs can be ...
- 41
2
votes
0
answers
90
views
Are the two meanings of "complete" related?
In the MathOverflow question "Are the two meanings of 'undecidable' related" and its answers, connections are drawn between undecidability of a statement over a theory and undecidability of ...
- 938
2
votes
2
answers
68
views
Does "defined by cases" only work for decidable sets or also for semi-decidable sets?
If $A,B\subseteq\mathbb{N}$ are disjoint decidable sets then it is
clear to me that function $f$ is defined as:
$f\left(x\right)=\begin{cases}
1 & \text{if }x\in A\\
2 & \text{if }x\in B\\
\...
- 149k
3
votes
0
answers
64
views
Is there a transfinite version of Post's Theorem?
Let $\emptyset^{(n)}$ denote the $n$th Turing jump of the empty set. Post's theorem states:
A set $B$ is $\Sigma^0_{n+1}$ if and only if $B$ is recursively enumerable by an oracle Turing machine with ...
- 2,370
2
votes
1
answer
115
views
Highest theorems in the arithmetical / analytical hierarchy in terms of formula complexity
I am posing this question based on this answer which asserts that the Riemann Hypothesis is a $\Pi_1^0$ statement while $\mathsf{P}$-vs-$\mathsf{NP}$ is a $\Pi^0_2$ statement ("for every code for ...
- 2,370
3
votes
1
answer
60
views
Using beta reduction on $ \lambda y. ( \lambda x. \lambda y. y x)(\lambda z. y z)$
I have a few questions regarding this exercise:
$$ \lambda y. ( \lambda x. \lambda y. y x)(\lambda z. y z)$$
This is what I have come up with:
$ \lambda y. ( \lambda x. \lambda \color{red}u. \color{...
- 893
5
votes
1
answer
167
views
Which countable ordinals are common to every $\omega$-model of ZF?
Consider the progression of larger and larger countable ordinals ($\omega$, $\omega^{\omega}$, $\epsilon_0$, the Veblen hierarchy, etc., described nicely here).
On the one, hand, it seems clear that ...
- 579
1
vote
0
answers
62
views
Show that A ⊆ N is semi-calculable if and only if there is a Σ-formula φ(x) such that φ defines A.
I am working through "A Friendly Introduction to Mathematical Logic" by Christopher Leary and Lars Kristiansen, and am currently stuck on this exercise:
Show that A ⊆ N is semi-calculable if ...
- 203
2
votes
1
answer
24
views
$(\lambda z. zy)(\lambda z. zy)$ - reducing using $\beta$ reduction and $\alpha$ conversion
Good day . I need to reduce the following expression of lambda calculus:
$(\lambda z. zy)(\lambda z. zy)$
Now, since I am having the variable $y$ in both the left and right pair of parentheses, I ...
- 893
1
vote
2
answers
27
views
Beta reduction on $(\lambda x . xu)(\lambda z. wzwz)yv$
I need to perform a reduction on the following lambda expression
$(\lambda x . xu)(\lambda z. wzwz)yv$
This is what I have done so far:
$(\lambda x . xu)(\lambda z. wyvwyv) = wyvwyvu$
However, my ...
- 613
1
vote
0
answers
53
views
Prove that NP ∩ co-NP closed under concatenation
I'm preparing for a test, and I've stumbled across the next question:
"Prove that the complexity class NP ∩ co-NP is closed under concatenation."
So my idea was that I know that a language $...
- 11
1
vote
2
answers
91
views
Simplyfing $(\lambda y. z)((\lambda x. x x)(\lambda x. x x))$
I need to simplify this expression.
$(\lambda y. z)((\lambda x. x x)(\lambda x. x x))$
However, what's interesting to me are two things:
Should I start simplifying $((\lambda x. x x)(\lambda x. x x))$...
- 613
2
votes
1
answer
70
views
Topological perspective of Rice-Shapiro theorem
Given a Gödel numbering $\phi_n$ of the partial recursive unary functions, the Rice-Shapiro theorem states
Let $\mathcal A$ be a family of partial-recursive unary functions such that its index set $...
- 343
5
votes
2
answers
178
views
Axiomatization of reducibility notions
In computability theory, there are many notions of reducibility (such as Turing reducibility, enumeration reducibility, many-one reducibility, etc.). I am curious—has there been any attempt to ...
- 747
0
votes
0
answers
52
views
Monadic logic with one binary relation is undecidable
The following quote is from Wikipedia:
Adding a single binary relation symbol to monadic logic, however, results in an undecidable logic.
What would be a reference for this result?
- 5,655
3
votes
2
answers
169
views
What, precisely, does it mean to represent an ordinal on a computer?
Two closely related questions about ordinals that I found quite confusing at first and couldn't find a satisfactory answer online (self-answering):
I've heard sentences like "$\omega^{CK}$ is ...
- 3,134
5
votes
0
answers
51
views
Number of ways to interleave two strings
An existing problem goes that:
Suppose we have two finite, ordered sequences x=(x1,…,xm) and y=(y1,…,yn). How many ways can we create a new sequence of length m+n from x and y so that the order of ...
- 51
1
vote
2
answers
74
views
Approximating Turing reducibility with finite subsets
Let $A$ and $B$ denote infinite subsets of $\omega$. Does there exist a quasi-ordering $\leq$ on $[\omega]^{<\omega}$ such that either:
$A \leq_\mathrm{T} B$ iff for all finite $x \subseteq A$, ...
- 8,115
2
votes
2
answers
125
views
Links between "productive" and "completely productive" sets?
In a computability course I met the two following notions :
A set $B$ is "completely productive" if there exists a total computable function $f$ such that : $\forall x \in \mathbb N \ (f(x) ...
- 3,280
0
votes
0
answers
29
views
Show that this set is $\Pi_1^0$-complete?
Let us call $A:= \{i \in \mathbb{N} \mid \varphi_i \ \text{is partial, computable and strictly increasing} \}$ and we want to show that $A$ is $\Pi_1^0$-complete (for the many-one reduction).
First, ...
- 3,280
2
votes
0
answers
41
views
The distribution of the composition of two random functions
Let $A$ and $B$ be two random functions of binary variables (e.g., two probabilistic algorithms). Then, on input $x \in \{0,1\}^*$, $A(x)$ outputs $y \in \{0,1\}^{f_A(|x|)}$ with probability $p_A(A(x) ...
- 191