Questions tagged [fixed-point]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
45 views

(Co)-induction, fixpoints and inference systems

I'm learning about induction and co-induction. From what I know, given a set of judgments $U$ and an inference system $\Phi \subseteq \wp(U) \times U$, where $(\left\{ h_1,\dots,h_n \right\}, c) \in \...
dalz's user avatar
  • 13
1 vote
0 answers
35 views

How much is decidability compromised within this restriction of the fixpoint combinator?

Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang. I considered this to be undesirable, and ...
Dannyu NDos's user avatar
4 votes
1 answer
106 views

Self referential hash function possible?

Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \, || \, y) = y$? In other words, if we concatenate its output with the input, the result will not change. Furthermore, ...
prog's user avatar
  • 93
3 votes
1 answer
426 views

How is the input to a BROUWER algorithm done

The Brouwer fixpoint theorem states that any continuous mapping $f$, from a convex, compact set to itself will contain a fixpoint. The Brouwer algorithm finds these (approximate) fixpoints. But how is ...
Andrew Baker's user avatar
6 votes
1 answer
227 views

Bisimulation and the Knaster–Tarski theorem: What does the least fixed point mean?

Given a suitable lattice and a monotonic function $F$, we can compute the bisimilarity of a labeled transition system (its greatest bisimulation) by computing the greatest fixed point of $F$ using ...
Karla's user avatar
  • 181
2 votes
0 answers
61 views

What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
brj's user avatar
  • 121
1 vote
0 answers
51 views

Is there a term for the inverse of a fixed-point operator?

When working with recursion it is often useful to find the least or greatest fixed points of a morphism, often using a fixed-point combinator. When working with recursion schemes, the inverse ...
Etherian's user avatar
1 vote
1 answer
37 views

How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.3 Data Flow Analysis says the following: The least solution. The ...
The Pointer's user avatar
7 votes
1 answer
351 views

How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?

The well-known Church encoding of natural numbers can be generalized to use an arbitrary (covariant) functor F. The result is the type, call it ...
winitzki's user avatar
  • 273
1 vote
0 answers
229 views

Find the fixed point of a recursive functional?

A functional is a function which takes another function as a parameter. The fixed point of a function is an input such that F(x) = x Given an example functional, <...
user116456's user avatar
0 votes
1 answer
140 views

Termination of Z combinator with call-by-value

I am trying to build my own λ-calculus interpreter. So far it supports both call-by-value and normal order. I now want to try recursion via fixed points. The $Y$ combinator works with normal order, ...
dlrlc's user avatar
  • 103
1 vote
1 answer
111 views

Fixed Points of Factorial Function

(This is taken from the book Semantics with Applications) I'm trying to determine the fixed points for the following block: ...
nz_21's user avatar
  • 123
0 votes
0 answers
35 views

Trying to determine Fixed Points

I'm basically trying to solve 4.2 (Taken from Semantics with Applications) As I see it, the functional F will be defined like so: ...
nz_21's user avatar
  • 123
5 votes
1 answer
1k views

Fixed point of hash

Are hashing algorithms constructed to guarantee that no fixed point exists? My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ...
Xophmeister's user avatar
6 votes
1 answer
409 views

Logical characterization of P versus NP problem (and references for least fixed point logic)

Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here: Thus, the question "is P a proper subset of NP" can be reformulated as "is existential ...
User7819's user avatar
  • 281
5 votes
2 answers
925 views

Why Does the Fixed Point Theorem Apply to Quines?

A quine is a program that outputs its own source code without taking in any input. An example would be this (taken from here) ...
Nathan Wood's user avatar
1 vote
2 answers
3k views

How does conversion from fixed-point to floating-point happen?

I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode) floating = fixed / 65536.0 Could you ...
ntrsBIG's user avatar
  • 13
1 vote
0 answers
38 views

Hebbian rule doesn't get to a fixpoint

I'm trying to implement an Hopfield Network for pictures of 32x32 bits either 1 or -1; I have these 3 pictures and I transform each of them in a vector of 1024 elements. Then I take the 3 vectors and ...
f.saint's user avatar
  • 11
1 vote
1 answer
160 views

Is Datalog negation and the built-in predicate $ \neq $ similar?

I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking ...
Milton Silva's user avatar
1 vote
1 answer
474 views

Neural Networks: Simulate the working of Dynamic Fixed Point representation of the weights on hardware

I am looking to implement a neural network on hardware using Verilog. I have completed and tested with floating point representation and a 20 bit fixed point representation. I want to further reduce ...
Abhinav Goel's user avatar
5 votes
2 answers
2k views

What is a fixpoint?

Could someone please explain me, what is a fix point? I caught the minimum explanation about fix point from the website: After infinitely many iterations we should get to a fix point where ...
zero_coding's user avatar
3 votes
1 answer
148 views

Why doesn't this quine-less language contradict Kleene's recursion theorem?

Kleene's recursion theorem implies that every Turing complete programming language that satisfies certain properties have quines. This website claims that this is incorrect, and that there is a Turing ...
Christopher King's user avatar
0 votes
2 answers
757 views

Decimal to Fixed Point Conversion

I am having trouble to get the intuition behind the following approach: We take the fraction point (say: .642) and continuously multiply by 2, taking whatever ends up right of the point as our next ...
Kevin Wu's user avatar
  • 101
3 votes
2 answers
72 views

Notation for a Kleene fixed point with a starting element

Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times ...
choeger's user avatar
  • 610
12 votes
2 answers
3k views

Why is least fixed point (lfp) important in program analysis

I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on ...
Ram's user avatar
  • 223