Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- [10:41] == rabb2t[pc] [4ec02d7f@gateway/web/freenode/ip.78.192.45.127] has joined ##googology
- [10:41] <rabb2t[pc]> hey
- [10:41] <Wojowu> Hey rabbit
- [10:42] <Wojowu> dafuq happened
- [10:42] <Wojowu> [09:41:42] --> rabb2t[pc] (4ec02d7f@gateway/web/freenode/ip.78.192.45.127) has joined ##googology
- [10:42] <Wojowu> [09:41:42] <-- rabb2t[pc] (4ec02d7f@gateway/web/freenode/ip.78.192.45.127) has quit (Changing host)
- [10:42] <Wojowu> [09:41:42] --> rabb2t[pc] (4ec02d7f@unaffiliated/rabb2tpc/x-1736421) has joined ##googology
- [10:42] <Wojowu> [09:41:42] <-- rabb2t[pc] (4ec02d7f@unaffiliated/rabb2tpc/x-1736421) has quit (Changing host)
- [10:42] <Wojowu> [09:41:42] --> rabb2t[pc] (4ec02d7f@gateway/web/freenode/ip.78.192.45.127) has joined ##googology
- [10:42] <Wojowu> All within a second
- [10:42] <rabb2t[pc]> o_O
- [10:43] <rabb2t[pc]> idk
- [10:49] <rabb2t[pc]> http://googology.wikia.com/wiki/User_blog:LittlePeng9/Creating_fast-growing_function
- [10:49] <rabb2t[pc]> "Although we can allow infinite programs, we will concern only finite ones."
- [10:49] <rabb2t[pc]> an infinite program? o_O
- [10:50] <rabb2t[pc]> what do you mean? an infinite amount of symbols?
- [10:50] <Wojowu> Yeah, it's possible to consider these
- [10:50] <Wojowu> The thing with Brainf*ck type programs is that you have a program tape, and there is a program head moving along it
- [10:50] <rabb2t[pc]> like TMs
- [10:50] <Wojowu> There is no program head in TM
- [10:51] <Wojowu> And no program tape
- [10:51] <rabb2t[pc]> oh
- [10:51] <Wojowu> You only have read/write head and tape
- [10:58] <rabb2t[pc]> I don't get what does "+"
- [10:59] <Wojowu> If only I remembered myself :P
- [10:59] <Wojowu> Let me sink into my own definition
- [11:00] <Wojowu> Okay
- [11:01] <Wojowu> So on the work tape, we can have one of the following characters: blank, >, <, +, [, ], #, {, }, $
- [11:01] <rabb2t[pc]> "+" is the thing I don't get
- [11:01] <Wojowu> When the program head reads a +, then it changes the symbol under the read/write head
- [11:01] <Wojowu> To the next symbol from this list
- [11:02] <Wojowu> So, if the read/write head was reading [, then it will change it to ]
- [11:02] <Wojowu> And it it was reading $, it would cycle it back to blank
- [11:02] <rabb2t[pc]> ok
- [11:06] <rabb2t[pc]> you say λ(n) and Λ(n) reaches (α -> ω^CK_α), do you still think it is true? I saw your forum post about Σ_k(n) not even reaching ω^CK_1
- [11:07] <Wojowu> Nah, I'm sure it doesn't
- [11:07] <Wojowu> Leaving aside what the hell it means that function reaches an ordinal
- [11:07] <rabb2t[pc]> does it "reaches" ω^CK_1
- [11:08] <rabb2t[pc]> wait
- [11:08] <Wojowu> I would say "no", but I'm not sure
- [11:08] <Wojowu> Again leaving aside what the hell it means that function reaches an ordinal
- [11:08] <rabb2t[pc]> can we say a system, i.e. SKI calculus, can "define" an ordinal?
- [11:09] <Wojowu> For SKI, I'm not sure
- [11:09] <rabb2t[pc]> e.g. a C program for FGH that handles ordinals using structs
- [11:09] <rabb2t[pc]> it would "define" ω, etc
- [11:09] <Wojowu> The problem with SKI is that it can't take input
- [11:10] <rabb2t[pc]> :V
- [11:10] <rabb2t[pc]> so, do you think a strong language like C++ can define, say, the TFB ordinal
- [11:11] <Wojowu> With correct definition of "define", yes
- [11:11] <Wojowu> And I know one definition which would work, if you are interested
- [11:11] <rabb2t[pc]> so, now I restate: "could the BF system you define [by adding an input system if needed] could define ω^CK_1"?
- [11:11] <rabb2t[pc]> and yeah I'm interested
- [11:12] <rabb2t[pc]> using structures?
- [11:12] <rabb2t[pc]> or a string that define it properties
- [11:12] <Wojowu> I have no clue what you mean by structure
- [11:12] <rabb2t[pc]> the "struct" keyword
- [11:12] <Wojowu> Still no clue
- [11:12] <Wojowu> But never mind
- [11:12] <rabb2t[pc]> or the "class" keyword in C++
- [11:12] <rabb2t[pc]> you don't know C/C++?
- [11:13] <Wojowu> I know C++, but I never used classes
- [11:13] <rabb2t[pc]> oh ok
- [11:13] <rabb2t[pc]> class (C++) and struct (C)
- [11:14] <Wojowu> If we are given a function f: N x N -> {0,1} (or to {false, true} if you prefer)
- [11:14] <Wojowu> Then we say f codes an ordinal a if relation on N x N induced by these pairs, which are mapped by f to 1 (or true) is a well order of order type a
- [11:15] <Wojowu> And then we can say that C can define a if we can define a function f in C which codes a
- [11:16] <Wojowu> (btw, unless I say otherwise, I'm ignoring finite ordinals here, because these need separate treatment)
- [11:16] <rabb2t[pc]> I wasn't thinking to that, but it works I guess
- [11:17] <Wojowu> If we agree on my definition, then C can define precisely recursive ordinals
- [11:18] <rabb2t[pc]> I was thinking to a class (e.g. an object with properties like "obj.index", methods "a.isWellOrdered()")
- [11:18] <Wojowu> I have no clue what that means :P
- [11:18] <rabb2t[pc]> lol
- [11:19] <rabb2t[pc]> do you know std::string?
- [11:19] <Wojowu> I think so
- [11:19] <Wojowu> Though I haven't really used them
- [11:19] <rabb2t[pc]> (or without the "std::" when "using namespace std;" is at the beginning of the program)
- [11:20] <rabb2t[pc]> "string" is a class
- [11:21] <rabb2t[pc]> is can have properties like his length, the numbers of "a"s, the number of times it has been modified, etc
- [11:21] <rabb2t[pc]> these are all stocked as variables
- [11:21] <Wojowu> Okay
- [11:22] <rabb2t[pc]> if you create an object A with "string A", it has all these properties. You can access them by "A.property-name", i.e. "A.length"
- [11:23] <Wojowu> (you mean e.g., not i.e.)
- [11:24] <rabb2t[pc]> (isn't it the same?)
- [11:24] <Wojowu> (i.e. means "that is", e.g. means "for example")
- [11:24] <rabb2t[pc]> (but "i.e." = "in example", no?)
- [11:25] <Wojowu> i.e. = id est, Latin for "that is"
- [11:26] <rabb2t[pc]> you can access them only if in the source code of the "string" class these are 1) defined, i.e. "A.ggregee" surely won't exists, 2) initialized (when you create the object, when you do "string A = "..."", a function call "constructor"/"initializer" is called in order to give "default" values to all properties, and 3) "public", some properties can't be accessed from the outside
- [11:26] <Wojowu> e.g. = exempli gratia, Latin for "for the sake of example"
- [11:26] <rabb2t[pc]> (thx)
- [11:26] <rabb2t[pc]> a function is called*
- [11:26] <rabb2t[pc]> oops nvm
- [11:26] <rabb2t[pc]> "a function called constructor/initializer is called"
- [11:27] <rabb2t[pc]> in structures, everything is public, there isn't any property you can't access (if defined)
- [11:29] <rabb2t[pc]> structures are limited to properties and doesn't have constructors, you must gives values to all properties yourself when creating the object A
- [11:31] <rabb2t[pc]> e.g. "struct S { int a; int b; char c; }" create a structure S with properties a, b and c. Then you can do "S variable; variable.a = 0; variable.b = 68465; variable.c = 'k'"
- [11:31] <rabb2t[pc]> and you have a var. "variable" that has properties a, b and c
- [11:33] <Wojowu> Okay, and how did you think we can use structures for ordinals?
- [11:34] <rabb2t[pc]> in classes you can add "methods", these are functions access by "object.method()". It can't be seen as "method(object)", but inside the method's code it can access all "private" properties
- [11:35] <rabb2t[pc]> you can program a class like sets
- [11:36] <rabb2t[pc]> there is a class "std::array" for finite sets
- [11:37] <rabb2t[pc]> for infinite sets, you could re-write the "array.getElementAt(n)" method as a function "f(n)=n" (for the set of all integers), or make it return other sets
- [11:38] <Wojowu> How would you code infinite set of infinite sets?
- [11:38] <rabb2t[pc]> e.g. the method "getElementAt(int n)" in the "omega_times_2" class would return "o + n" where o is an object of the class "omega" (you also need to create a method "operator+" for the omega class)
- [11:39] <Wojowu> Okay, I think I see your point
- [11:39] <Wojowu> I guess it would again lead to all recursive ordinals, but I'm honestly now sure
- [11:40] <rabb2t[pc]> "omega_times_3" can be encoded either, as well as "omega_squared"
- [11:42] <Wojowu> I can't say that I understand completely how this would work, but I do get an idea
- [11:42] <rabb2t[pc]> a property of "omega_times_n" could store the value of n. For n=1, "getElementAt(n)" returns n, otherwise "o + n", where o is a copy of the original object, with the property "n" decreased
- [11:43] <rabb2t[pc]> "omega_squared" returns a "omega_times_n" object
- [11:43] <Wojowu> How would define infinitely many different classes?
- [11:43] <rabb2t[pc]> what do you mean?
- [11:44] <rabb2t[pc]> "omega_times_n" I was talking of a class NAMED "omega_times_n"
- [11:44] <Wojowu> Oh, okay
- [11:45] <rabb2t[pc]> it would be a bit hard, but you could then define "omega_cubed", and so on
- [11:45] <Wojowu> So suppose I give you a class "my_ordinal"
- [11:45] <rabb2t[pc]> but it would take time
- [11:45] <Wojowu> How do you determine what ordinal it would code?
- [11:45] <rabb2t[pc]> its properties
- [11:45] <Wojowu> ?
- [11:46] <rabb2t[pc]> idk, e.g. make a struct that helps to identify the ordinal, with properties like "isSuccessor", "isMultiplicative", ...
- [11:46] <rabb2t[pc]> as long as you define it
- [11:47] <Wojowu> For your idea to work, you need to have something that determines if a class codes an ordinal, and if so, what this ordinal is
- [11:47] <Wojowu> Otherwise this is just fuzzy handwaving
- [11:48] <rabb2t[pc]> you can
- [11:48] <rabb2t[pc]> wait
- [11:48] <rabb2t[pc]> i try to translate the name :V
- [11:48] <rabb2t[pc]> a class can "inherit" of another class
- [11:48] <Wojowu> What does that mean, and how does it help?
- [11:49] <rabb2t[pc]> the class "ifstream" inherits from "istream" and "fstream", it gets all the properties/methods these have
- [11:49] <rabb2t[pc]> AND,
- [11:50] <rabb2t[pc]> you can do "fstream F1 = F2"; where F2 is an ifstream
- [11:50] <rabb2t[pc]> it's hard to explained
- [11:50] <rabb2t[pc]> but if "omega" inherits from "ordinal", you can do "omega a; ordinal b; b = a"
- [11:50] <rabb2t[pc]> because an object "omega" is an object "ordinal"
- [11:51] <rabb2t[pc]> since "omega" inherits from "omega"
- [11:51] <rabb2t[pc]> oops
- [11:51] <rabb2t[pc]> from "ordinal"
- [11:51] <Wojowu> I think the problem here now is, how do you define object "ordinal"
- [11:53] <rabb2t[pc]> you can leave that class with undefined methods: just declare them. If you declare "Ordinal getElementAt(int n)" in "Ordinal" but don't define it, then all class that inherits from "Ordinal" will have to define it. Then, you can do "Ordinal A; Omega B; A = B; A.getElementAt(100)"
- [11:53] <rabb2t[pc]> i.e. "Ordinal" says what are the methods and properties ALL ordinals will have
- [11:53] <rabb2t[pc]> should*
- [11:53] <rabb2t[pc]> that all ordinals classes* should have
- [11:54] <Wojowu> Okay, and what would be these methods and properties?
- [11:54] <rabb2t[pc]> idk
- [11:54] <rabb2t[pc]> eventually a comparaison method
- [11:54] <rabb2t[pc]> to determing which ordinal A or B is bigger
- [11:55] <rabb2t[pc]> you can put what you want
- [11:55] <rabb2t[pc]> you can make a list of everything you expect from an "ordinal" object in C++, then program it
- [11:55] <Wojowu> So it seems like right now we are getting to the point where your idea is something to heavily work on
- [11:55] <rabb2t[pc]> =D
- [11:56] <rabb2t[pc]> then getFundamentalSequence(n) for "a[n]", also a.isWellOrdered(), and so on
- [11:56] <Wojowu> Because we need a way of determining if class defines an ordinal, and you are pretty much saying "class is an ordinal if it satisfies all the properties which ordinal class satisfies"
- [11:57] <Wojowu> Which is saying that "apple is red if it is red"
- [11:57] <rabb2t[pc]> just "if it inherits from the class "Ordinal"", no?
- [11:57] <Wojowu> But you didn't define class Ordinal
- [11:58] <rabb2t[pc]> you can make an "interface": it only will have undefined methods, but all methods you expect from a class "that is an ordinal"
- [11:58] <rabb2t[pc]> all classes that implements the interface inherits the methods and must define them, otherwise these classes can't be used
- [11:58] <Wojowu> And you did it again, you didn't say what these methods are, you just said "methods which we expect from an ordinal"
- [11:59] <rabb2t[pc]> we didn't list them, but we could
- [11:59] <rabb2t[pc]> now?
- [11:59] <Wojowu> All this time I'm trying to convince you that listing them is the actual problem
- [11:59] <rabb2t[pc]> why?
- [12:00] <Wojowu> If you don't think it's a problem, then list me these methods
- [12:00] <rabb2t[pc]> why couldn't we list all these?
- [12:01] <Wojowu> I'm not saying we can't
- [12:01] <Wojowu> It's a problem because it's hard
- [12:01] <rabb2t[pc]> I'm not saying it's easy :V
- [12:01] <Wojowu> Because your description of ordinal classes doesn't say at all what properties these classes have
- [12:01] <rabb2t[pc]> what about a blog post, so everyone could propose something
- [12:01] <Wojowu> You say that they have to be well-ordered - what does it mean for a class to be well-ordered?
- [12:02] <Wojowu> Go ahead, make one
- [12:02] <rabb2t[pc]> :O
- [12:02] <rabb2t[pc]> I'm not good at explaining
- [12:02] <Wojowu> That's too bad
- [12:07] <rabb2t[pc]> [11:42] <rabb2t[pc]> a property of "omega_times_n" could store the value of n. For n=1, "getElementAt(n)" returns n, otherwise "o + n", where o is a copy of the original object, with the property "n" decreased
- [12:07] <rabb2t[pc]> all ordinal classes would be based on that
- [12:07] <rabb2t[pc]> I explain,
- [12:08] <rabb2t[pc]> based on "smaller" classes
- [12:08] <rabb2t[pc]> smaller classes + diagonalization for limit ordinla
- [12:08] <rabb2t[pc]> ordinals*
- [12:09] <rabb2t[pc]> is it always true that limit of recursive are recursive?
- [12:09] <Wojowu> How does it help you if I give you just some class "my_class", and ask you to determine if it codes ordinal, and if som which ordinal?
- [12:09] <Wojowu> No, w_1^CK is limit of recursive ordinals
- [12:09] <Wojowu> And is not recursive itself
- [12:09] <rabb2t[pc]> I mean, obtained by diago.
- [12:10] <Wojowu> ?
- [12:10] <rabb2t[pc]> e.g. w+1, w+2 ,... -> w+w = w2
- [12:10] <Wojowu> This limit of recursive ordinals is recursive
- [12:10] <Wojowu> But this need not be the case in general
- [12:11] <rabb2t[pc]> (I'm trying to get the result "ordinal classes [like I described them] can't define the Church-Kleene Ordinal")
- [12:11] <rabb2t[pc]> (it must be provable)
- [12:11] <rabb2t[pc]> (I guess)
- [12:12] <Wojowu> You didn't define what "ordinal classes" are
- [12:12] <Wojowu> You have just described few of them
- [12:12] <rabb2t[pc]> describe*
- [12:14] <rabb2t[pc]> I mean by analogy, we could compare the process of using the property "n" as below as a way to construct ordinals (i.e. "o+n" => "o [any operation, but that C++ can do, so recursive] n" with o a smaller ordinal) can't construct CK_1
- [12:15] <Wojowu> Here is what you are doing wrong:
- [12:15] <Wojowu> You gave an example of how this works for very small ordinals
- [12:15] <rabb2t[pc]> or, "limi of recursive operations on recursive ordinals can't reach CK_1"
- [12:16] <rabb2t[pc]> limits*
- [12:16] <Wojowu> But you didn't specify at all what you can do or can't do for such construction in general
- [12:16] <Wojowu> What are recursive operations?
- [12:16] <rabb2t[pc]> e.g. that a TM could do
- [12:17] <Wojowu> TM can't work with ordinals
- [12:17] <rabb2t[pc]> ok, wait
- [12:17] <Wojowu> Sure, I have time
- [12:19] <rabb2t[pc]> a "C++ ordinal" (not "ordinal") is a C++ object (i.e. a variable that is defined using a class) that is defined using the class "CxxOrdinal" or any class that inherits from this class
- [12:21] <Wojowu> What's "CxxOrdinal"?
- [12:21] <rabb2t[pc]> a class
- [12:21] <rabb2t[pc]> I'm not talking of mathematical objects
- [12:21] <Wojowu> But what class is this?
- [12:21] <rabb2t[pc]> I'm defining it, lemme write :V
- [12:21] <Wojowu> Okay
- [12:25] <rabb2t[pc]> the CxxOrdinal class has property "int n", "int k" and methods "bool isLimit()", "bool isFinite()", "CxxOrdinal FS(CxxOrdinal n)", "CxxOrdinal FS(int n)", and "FS(CxxOrdinal n)" is defined as follow: "CxxOrdinal FS(CxxOrdinal &o) { return o.FS(k) }"
- [12:25] <rabb2t[pc]> (explanations incoming)
- [12:26] <rabb2t[pc]> I will do analogies with ordinals just to make it understandable
- [12:26] <Wojowu> You could write blog post about this
- [12:26] <Wojowu> So that all of this is in one place
- [12:28] <rabb2t[pc]> I will put the whole discussion on pastebin, then I'll use it to make a blog post when I'll have time
- [12:28] <Wojowu> Okay
- [12:28] <rabb2t[pc]> "FS(n)" is by analogy α[n]: if n is a finite number, must be defined by the class that inherits
- [12:30] <rabb2t[pc]> if n is limit, return α[n[k]] (nvm the definition I wrote, I'll re-do it), where k is some integer we need (because I don't know what to use else :V)
- [12:30] <rabb2t[pc]> wait,
- [12:30] <rabb2t[pc]> nvm all that stuff
- [12:30] <Wojowu> Before you continue, question
- [12:31] <Wojowu> Does that somehow disallow us having class which is the set of all integers?
- [12:31] <rabb2t[pc]> I'm doing like if α[β] exists for limit β :V I wasn't thinking to that
- [12:31] <rabb2t[pc]> why would it?
- [12:32] <Wojowu> Because set of integers is not well-ordered
- [12:32] <Wojowu> I meant having this class as an ordinal
- [12:32] <rabb2t[pc]> so I remove my "FS(n)" property for CxxOrdinal n
- [12:32] <rabb2t[pc]> it isn't really sets
- [12:33] <Wojowu> Earlier you were saying these are sets
- [12:33] <Wojowu> (or are meant to be sets, sth like that)
- [12:33] <rabb2t[pc]> since I started talking of CxxOrdinal, I stopped doing like these classes really represents ordinals
- [12:34] <rabb2t[pc]> I'm trying to make something comparables to ordinalsfor C++,
- [12:35] <rabb2t[pc]> I don't know how to make a class that really is an ordinal (i.e. that has the same properties)
- [12:35] <rabb2t[pc]> because I don't know all these properties
- [12:36] <Wojowu> There is really only one property which ordinal has to satisfy: its every subset has to have a smallest element
- [12:37] <rabb2t[pc]> I think we could say that C++ ordinal O correspond to the ordinal that is set "O.FS(0), O.FS(1), O.FS(2), ..."
- [12:38] <Wojowu> You mean limit ordinal
- [12:38] <rabb2t[pc]> yeah
- [12:39] <rabb2t[pc]> so, I have "class CxxOrdinal { public: int n; bool isLimit(); CxxOrdinal FS(int n); }" but it doesn't work, because FS always return a CxxOrdinal, but there must be the "base case" (i.e. omega) that returns to the "int" type
- [12:40] <rabb2t[pc]> i.e. I can't code FS(n) = n with that stuff :V
- [12:41] <Wojowu> I can't really help you with that
- [12:41] <Wojowu> If you want to discuss this with someone more knowledgeable about these things, wait for vell to come
- [12:41] <Wojowu> He is coming pretty much every evening
- [12:42] <rabb2t[pc]> I'll have to go eat in a few
- [12:43] <Wojowu> Okay
- [12:43] <rabb2t[pc]> I see the complicated solution (adding "isFinite(), getNaturalValue()", etc) but there should be an easier way
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement