Page 1 of 1

"Fixed Points"

Posted: Mon Oct 15, 2018 9:47 pm
by kenbrooker
Per Wikipedia, a "Fixed Point" occurs when the function f(c) = c.
There's a similarly simple graph too...

Per another reputable source:
"I call X a Fixed Point of [function] M if X yields M(X)."

In this case, X is a string and X is a function, a function of itself.
For example, if X = 33233 then X "yields" 33233233233 and
if M = 3 then M(X) = 33233233233, so "X yields M(X)" and
33233 is "called" a Fixed Point of M = 3.

For M = 3, 33233 is indeed a... Significant Point but
my problem is that nowhere am I seeing
an instance of "f(c) = c;" not for
function M; not for function X.

Any ideas welcome...

Re: "Fixed Points"

Posted: Tue Oct 16, 2018 6:30 am
by jaap
kenbrooker wrote:
Mon Oct 15, 2018 9:47 pm
In this case, X is a string and X is a function, a function of itself.
In what case? In what context do you have strings that are also functions?

It is hard to tell what misunderstandings you might have if you don't show the original text that you might be misunderstanding.

Re: "Fixed Points"

Posted: Wed Oct 17, 2018 1:09 am
by kenbrooker
Thanks for asking

"In what case?" Good question. At the risk of boring you, here's the context
(which I recommend just skimming) --
Arnie next explained to me that most of the previous
results were but special cases of one very lovely general
fact involving the important concept of Fixed Points.

I shall use the symbol M to denote any expression having
the property that for every expression X, the expression
M2X yields some expression Y, and for any Z other than
2X that yields X, MZ yields the same Y as is yielded by
M2X. Such an expression M, I will call a Special Expression.
Thus for any Special Expression M, if Y1 and Y2 yield the
same expression, then MY1 and MY2 will yield the same
expression. Any expression composed of C, R, and V is
special. For any Special Expression M, and any
expression X, by M(X) I shall mean the expression yielded
by M2X (or by MY for any Y that yields X). For example
R(X) is the repeat of X (since R2X yields XX) and V(XYZ)
is the reverse of XYZ (since V2XYZ yields ZYX).
Is this clear so far?

If I was in your shoes only that next to last sentence might be clear and
that's all that needs to be clear when the source then states --
Now I call X a Fixed Point of [function] M if X yields M(X).
Many of the previous problems were tantamount to finding
Fixed Points. For example, finding an X that yields its
own repeat is finding a Fixed Point of [M = ] R; an X that
yields its own reverse is simply a Fixed Point of [M = ] V;
and so forth.
Let me add another example of all of the above to
clarify the meaning of "X yields" --

For M = R, the Repeat function, if I choose the string (and
function) X to equal R32R3 then X yields R32R3R32R3 and
M(X) = R(R32R3) = R32R3R32R3, so X = R32R3 is a
Fixed Point of function M = R in this case.

And it is my interpretation that X is a string and a "function"
(of itself!). You can interpret X as the concatenation of
right-to-left Operators and an Operand, with the two
separated by the first '2' you come to from the left.

The discovery of what X yields M(X) is not at all obvious at first.
X = R32R3 as a string/function is evaluated, from right to left, as --
2R3 = R3 then 3(R3) = R32R3 then R(R32R3) = R32R3R32R3.
Whereas M(X) = R(X) = R(R32R3) = R32R3R32R3 is a
simple, straightforward repeat of X.

As you may observe, 2X simply yields X and 3(X) yields
X2X (and 2X is simply the string concatenation of 2 and X,
not 2 times X; and, e.g. 3(X) does not equal 3X ).

Getting back to the Wikipedia definition of a Fixed Point
where f(c) = c, I can think of no X where M(X) = X but
the source calls X a Fixed Point of [function] M if
X yields M(X) or, if M(X) equals what X yields,
NOT if M(X) equals X. That's my problem...

EDIT: Well I guess using the Reverse function V --
V(X) does equal X for X as any palindrome but
by the source's definition the Fixed Point of
the function V(X) occurs at X = V32V3...

Re: "Fixed Points"

Posted: Wed Oct 17, 2018 8:46 am
by jaap
Oh, it's the unmistakable work of Raymond Smullyan.

The strings we are working with are expressions. Just like an ordinary arithmetical expression like "4+5" can be evaluated to yield "9", these strings have their own type of arithmetic that can be used to evaluate them and yield another string.

You are right that here the definition of a fixed point of a function is slightly different to what we are used to. This is partly because the functions in this context are functions that work on arbitrary strings. With ordinary numerical functions it does not matter how its input is formulated, i.e. if f takes numerical input then f(4+5) is the same as f(9). For functions with a string input, the way the input is expressed makes a difference because it is a different string.

So in this context, the expression X is defined to be a fixed point of the function M() if:
M(X as a string) = [X evaluated]

As for why the right hand side in this definition is evaluated, I guess it's just because it is more useful.

Re: "Fixed Points"

Posted: Wed Oct 17, 2018 7:28 pm
by kenbrooker
Much Obliged

I am impressed that you identified the source (! and
hopefully someday you will see why I didn't) and
maybe "usefulness" is why Smullyan defered to --
"I call X a Fixed Point..." as opposed to what
normally, formally defines a "Fixed Point".

Fixed Points being the terminating condition* when
recursively computing, I am left wondering
if that condition still holds?
*like Factorial(0) = 1

My guess is... Yes!


ps - WOW...
You are only
4 Problems
away from
Level 16!!

Re: "Fixed Points"

Posted: Sun Oct 21, 2018 6:11 pm
by kenbrooker
Came across the theory of Coincidence Points where f(x) = g(x) and, as two and three Posts above,
where M(X) = Xyields(X) is "called" a Fixed Point.

Coincidence Points theory is a generalization of Fixed Points theory where
a key characteristic is a guaranteed solution, that is
there must be some X that yields M(X).