"Fixed Points"

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

"Fixed Points"

Post 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...
Last edited by kenbrooker on Wed Oct 17, 2018 4:06 am, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
User avatar
jaap
Posts: 587
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: "Fixed Points"

Post by jaap »

kenbrooker wrote: Mon Oct 15, 2018 10:47 pmIn 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.
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: "Fixed Points"

Post by kenbrooker »

Thanks for asking
jaap,

"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?
jaap,

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...
Last edited by kenbrooker on Sat Oct 20, 2018 6:11 am, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
User avatar
jaap
Posts: 587
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: "Fixed Points"

Post 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.
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: "Fixed Points"

Post by kenbrooker »

Much Obliged
jaap,

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!

Thanks
Again!!

ps - WOW...
You are only
4 Problems
away from
Level 16!!
Last edited by kenbrooker on Tue Oct 23, 2018 12:19 am, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
User avatar
kenbrooker
Posts: 187
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: "Fixed Points"

Post 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).
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image
Post Reply