Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Newsgroups | sci.math |
| Subject | Re: Ordinals |
| Date | 2024-03-01 20:52 +0100 |
| Message-ID | <urtblr$qfb8$1@solani.org> (permalink) |
| References | (9 earlier) <urptma$abti$2@i2pn2.org> <2NRiNAMtOqLljuoKQ0Z4UbqiHbE@jntp> <urrh33$cbpp$7@i2pn2.org> <thicnWRrTbih0Hz4nZ2dnZfqn_udnZ2d@giganews.com> <urtarb$qese$1@solani.org> |
Know that one is the secret and source of all the cardinals.
-- Abraham ibn Ezra (1153)
But have mercy to me. So far I thought in ordinal
anlysis of programs, we would simply take the
tree of execution, and this is somehow an ordinal
for a terminating program? But whats the tree
repectively ordinal for for example 3! = 6 ?
Are all finite ordinals the same or not?
For example the ordinals 0, 1, 2, 3, with von
Neumann succeessor are:
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{{},{{}}}}}.
Or as trees, * = empty set, o = non-empty set:
0 = *
1 = o
|
*
2 = o
/ \
* o
|
*
3 = o
/ | \
* o o
| / \
* * o
|
*
But what about this tree, it has also no infinite decend,
but what property is missing to make it an ordinal?
? = o
/ | \
* o o
| |
* o
|
*
Or as a set:
? = {{},{{}},{{{}}}}.
Why is it not an ordinal?
P.S.: I tried to find an answer here, but I guess
I am too lazy to read it. Its starts with the funny
quote and has funny pictures in it:
Trees, ordinals and termination
N Dershowitz · 1993
https://link.springer.com/content/pdf/10.1007/3-540-56610-4_68.pdf
Mild Shock schrieb:
> Somehow I am quite new to the ordinal analysis
> that Alan Turing started. Nice find Gödel introduces
> a nice notion in his incompletness paper,
>
> namely he says a function is primitive recursive,
> to degree N, if the primitive recursion schema is
> applied N times. So I guess this definition of
>
> factorial would then have degree 3, since 'R' is used 3 times:
>
> /* The R combinator */
> natrec(_, 0, X, X) :- !. % attention, not steadfast
> natrec(F, N, X, Z) :- M is N-1, natrec(F, M, X, Y), call(F, Y, Z).
>
> plus(X, Y, Z) :- natrec(succ, X, Y, Z).
>
> mult(X, Y, Z) :- natrec(plus(X), Y, 0, Z).
>
> step((X,Y),(Z,T)) :- succ(X,Z), mult(Z,Y,T).
>
> factorial(X,Y) :- natrec(step,X,(0,1),(_,Y)).
>
> Works fine, although eats quite some computing resources,
> i.e. 9_303_219 inferences, since it must form
> 3268800 successors:
>
> ?- factorial(10,X).
> X = 3628800.
>
> ?- time(factorial(10,X)).
> % 9,303,219 inferences, 0.578 CPU in 0.617 seconds
> (94% CPU, 16092054 Lips)
> X = 3628800.
>
> Ross Finlayson schrieb:
>> ... fourier my ass, what has it to do with ordinals ...
>>
>
Back to sci.math | Previous | Next — Previous in thread | Next in thread | Find similar
Re: Ordinals "markus...@gmail.com" <markusklyver@gmail.com> - 2024-02-20 11:35 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-20 20:54 +0100
Re: Ordinals "mitchr...@gmail.com" <mitchrae3323@gmail.com> - 2024-02-20 11:59 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-20 12:15 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-20 12:27 -0800
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-20 17:02 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-20 19:36 -0800
Re: Ordinals Mild Shock <bursejan@gmail.com> - 2024-02-21 05:47 -0800
Re: Ordinals Mild Shock <bursejan@gmail.com> - 2024-02-21 05:50 -0800
Re: Ordinals Mild Shock <bursejan@gmail.com> - 2024-02-21 06:16 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-21 10:24 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 09:03 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 09:11 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 10:16 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:20 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:22 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 19:40 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:00 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 10:55 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:08 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:13 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 11:01 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:11 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-22 20:13 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-22 14:34 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-22 11:39 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-02-23 00:41 +0100
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-21 08:33 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-21 12:59 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-22 13:00 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-22 11:13 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-23 08:47 +0000
Semanticists candy (Was: Ordinals) Mild Shock <janburse@fastmail.fm> - 2024-02-26 12:58 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-27 14:25 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-27 11:59 -0800
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-27 20:05 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-27 17:24 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-28 09:48 +0000
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-02-28 06:52 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-28 17:24 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-02-28 17:07 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-29 08:23 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-02-29 07:35 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-02-29 19:25 +0000
Re: Ordinals "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-02-29 13:48 -0800
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-02-29 22:12 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-02-29 19:36 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 20:38 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 20:52 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 21:08 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-03-01 15:56 -0500
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 22:53 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 23:11 +0100
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-01 23:33 +0100
Re: Ordinals Jim Burns <james.g.burns@att.net> - 2024-03-01 19:41 -0500
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-03-01 20:15 -0800
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-03-02 10:49 -0800
Re: Ordinals Mild Shock <janburse@fastmail.fm> - 2024-03-02 20:40 +0100
Re: Ordinals Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-03-01 14:45 -0800
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-01 08:47 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-03-01 09:44 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-01 18:29 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-03-01 14:00 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-02 12:36 +0000
Re: Ordinals Richard Damon <richard@damon-family.org> - 2024-03-02 09:22 -0500
Re: Ordinals WM <wolfgang.mueckenheim@tha.de> - 2024-03-02 15:25 +0000
Re: Ordinals "mitchr...@gmail.com" <mitchrae3323@gmail.com> - 2024-02-20 17:21 -0800
RSemanticists candy (Re: Ordinals) [Addendum] Mild Shock <janburse@fastmail.fm> - 2024-02-26 13:01 +0100
csiph-web