Questions tagged [fixed-points]
The fixed-points tag has no usage guidance.
14
questions
3
votes
1
answer
123
views
Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?
Given a polynomial functor $F$, its initial algebra is denoted by $\mu X.F(X)$.
Now, if $F$ is a 2-variable polynomial functor, $Y \mapsto \mu X.F(X,Y)$ turns out to be functorial and we can, again, (...
- 199
3
votes
0
answers
72
views
Generalizing Quines: Outputting an Arbitrary Function of Source Code
A Quine is a (non-empty) program $P$ that takes no inputs and returns its own source code $\langle P\rangle$ as the only output. For a function $f$ (with appropriate domains and range) define an $f$-...
- 119
4
votes
1
answer
181
views
Computing an approximate root of a two-dimensional monotone function
Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions:
For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is ...
- 2,078
0
votes
1
answer
190
views
4
votes
1
answer
135
views
Is there a relation between the techniques used by Dan Willard, versus those of Brown and Palsberg, to exclude diagonalization?
This question extends my inquiry from a previous post [0].
Dan Willard's Self-Justifying Axiom Systems/Self-Verifying Theories [1] and Brown and Palsberg's self-interpreter for F-Omega [2] both employ ...
- 81
2
votes
0
answers
94
views
Is there a relationship between Brown and Palsberg's Self-Interpreter for F-Omega and Lawvere's Fixed Point Theorem?
Brown and Palsberg [0] demonstrated an self-interpreter for F-Omega. To do so, they perform "a careful analysis of the classical theorem [of the impossibility of self-interpretation by total ...
- 81
8
votes
4
answers
472
views
Type theory and fixed points of datatypes
For the purposes of this question, say that a datatype is a type constructor with one type parameter (this is sometimes called a type operator).
In Haskell, we can define a fixed point ...
- 900
9
votes
0
answers
195
views
Is it known how much computation a fixed-point combinator gets you?
It is well-known that the SKI combinators are enough to get universal computation, though the original version of combinatory calculus used BCKW. However, it is possible to get a fixed-point ...
- 190
3
votes
1
answer
321
views
Fixed points of fixed-point combinator?
A fixed point f of a fixed-point combinator would be a function that has itself as a fixed point: f(f) = f. The only such ...
- 143
9
votes
0
answers
247
views
Which version of KAKUTANI does lie in PPAD?
The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
- 546
7
votes
1
answer
274
views
The originator of the fixed point theorem for DCPOs
Pataraia proved in
"A constructive proof of Tarski’s fixed-point theorem for dcpo's", presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997
that in a ...
user49915
0
votes
1
answer
83
views
Solving recurrence [closed]
Let $f(x) = 3/2 - \sqrt{2 - 8x^2}$. I am interested in the recurrence $Y_0 = 0$ and $Y_{i+1} = f(Y_i) = f(f(Y_{i-1})) = ... = f(f(f(f(... f(0) ...))))$. A quick plot shows that $Y_i$ converges to $1/6$...
- 79
1
vote
0
answers
100
views
Deciding reachability under iterated independent polynomial mapping
For any $1\leq i\leq m$, $f_i: \mathbb{Q}\rightarrow \mathbb{Q}$ is a polynomial mapping over $x_i$, where $\mathbb{Q}$ is the set of rationals. For $\vec{a}_0=(a_1, \cdots, a_m)\in \mathbb{Q}^m$, we ...
- 21
6
votes
0
answers
219
views
Relationship between Pataraia's theorem and inductive-recursive definitions?
Pataraia's fixed point theorem gives a constructive proof of the fact that if you have a monotone function $f$ on a DCPO, then it has a least fixed point. I've frequently used this fixed point theorem ...
- 32.4k