Carmack On Future Graphics Engines

Discussion in 'General 3D Technology' started by MikeC, Oct 31, 2002.

  1. OpenGL guy

    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    2,357
    Likes Received:
    28
    That's not what they Democoder is arguing. Democoder is arguing that the limit of the ClassX sets is countable. But the limit of the ClassX sets is not countable because you have numbers of infinite length. The integers do not contain numbers of infinite length.

    From arjan's post:
    This converges to "2^infinity" in the limit. I.e. you get programs with bit patterns like 101001000100001..., 10110111011110..., etc. The are analogous to the irrational numbers in the real line.
     
  2. Nagorak

    Regular

    Joined:
    Jun 20, 2002
    Messages:
    854
    Likes Received:
    0
    My main point is everyone is going crazy saying "OMG such great graphics" when in fact the artwork isn't even that impressive. There's more to a game than shadowing, lighting, etc. id does make good engines, but Doom3 isn't half as impressive as everyone is making it out to be. It could be, but not with their lack of good artwork and game (not engine) design.
     
  3. Nagorak

    Regular

    Joined:
    Jun 20, 2002
    Messages:
    854
    Likes Received:
    0
    :roll: :roll: :roll: :roll: :roll:
     
  4. DemoCoder

    Veteran

    Joined:
    Feb 9, 2002
    Messages:
    4,733
    Likes Received:
    81
    Location:
    California
    False. Your example is the same example Cantor used to prove the non-existence of a mapping between the integers and the reals. Simply write your list of integers with decimal point in front out in the limit, and you can trivially construct reals which are not included in the list.

    Why are we arguing about this? The following facts have already been proven and are in your textbook:

    1. The set of all programs, theorems, languages, et al, are countable (look in theory of computation textbook). This works just like Goedel numbering. Any program or theorem in any language can be assigned a unique integer. There are no programs which cannot be numbered by the integers, therefore the set of all possible programs are countable.

    2. the union of countably many countable sets is countable (should be in your set theory book. also,look http://www.wikipedia.org/wiki/Countable


    ClassX is simply the class of all possible programs (or subset thereof). This set is countable. Class1 ... ClassN are also countable subsets. The union of these subsets is countable. QED.

    Edit: It appears we have differing ideas of what ClassX is, perhaps that's the confusion. ClassN is simply the class of all N-pass algorithms. ClassX is simply ClassN in the limit. Any given ClassN algorithm can be reduced to a class < N but augmenting a machine to run it in fewer passes.

    You appear to assume that there is the possibility that each pass can be infinite. That is, you are executing two infinitely long shaders in each pass and ClassX could be infinitely many passes each consisting of infinitely long shaders. This is false. Our shaders are limited by the power of the Church-Turing thesis. There are no infinitely long programs and we assume nothing more powerful than a turing machine.

    If you cannot assign an integer to a shader, it is not a valid program.
     
  5. OpenGL guy

    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    2,357
    Likes Received:
    28
    You are still talking about the union.
    This is not a union we are talking about now: We are talking about a limit. I already said in a previous post that the union of these sets is countable. However, the limit of these sets is uncountable.

    Here's why:
    1
    10
    101
    1010
    10100
    101001
    etc.

    These are elements in the union. However, it's limit 1010010001... is not.

    I don't disagree with this. What I have been saying is that the limit (i.e. let the length of the programs go to infinity) is not. The limit contains the limit points, many (all, from a measure theory point of view) of which lie outside the union.

    Read my post:
    http://www.beyond3d.com/forum/viewtopic.php?p=51632#51632
    It sounds like you are talking about a limit in the line I quoted.
     
  6. DemoCoder

    Veteran

    Joined:
    Feb 9, 2002
    Messages:
    4,733
    Likes Received:
    81
    Location:
    California
    We are talking about a union of sets. Each set is defined to be countable, even in the limit. We have a countable number of sets, each of whose cardinality is countable, therefore the union is countable.


    Your argument is tautological. You start out with an uncountable sequence of sets and end up with the result that a transcendental number is not in the union. Well, that's a surprise. I could just as easily propose the following: Let Sk = {open interval set of all reals between 0 and 1 with decimal point removed}. 1.0 is not in this set. Each number in my set is a legal integer digit string, therefore the integers are uncountable?

    The sequence you propose of sets (10, 10100, 101001000, 10100100010000, ...) is uncountable. There is no bijection between the integers and this sequence. Here's another example: (k > 0) Sk = { k if Theorem K is true, -k otherwise } or Sk = {k if Program K halts, -k otherwise }. Choose any unprovable, or uncountable condition and generate your own.


    Remember, the requirements are: countably many sets, each set countable, produces countable union. You are not allowed to define a limit sequence of sets which is uncountable. If you keep all of your math in the real of integers and Turing computable numbers, you will that it works out.

    The fact remains: All possible computer programs can be ordered and assigned integers. Any possible sequence of such programs (and the logic to construct such a sequence would have to be a program itself which itself has a number!) is countable.

    I can claim that there exist sequences that can be constructed "in theory" and invoke the axiom of choice (e.g. the sequence of all programs that halt), but for which no possible program can be constructed to produce such a sequence. This by no means means that the set of all computer programs is uncountable! If I start out by choosing something which makes a bijection into the integers impossible, I end up with uncountability. No surprise.


    All it means is that there are some sequences for which no decision procedure exists. You can invoke the axiom of choice all you want to claim that the existence of such a set means the limit is uncountable, I will maintain that if we can produce a set of decision procedures for classifying multipass programs, such a sequence of programs would be countably infinite.

    (the classification procedure itself proves the countability, since any procedure would enumerate all possible programs. It literally *IS* the mapping from the integers.)
     
  7. OpenGL guy

    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    2,357
    Likes Received:
    28
    If you're not going to read what I post, then why bother replying?
    This is a limit. The limit of these sets is not countable. I don't have any problem with the union being countable, but that's not what your above statement is saying.

    The limit contains programs of infinite length, these are not mappable to the integers in any meaningful way.

    That's enough from me.
     
  8. DemoCoder

    Veteran

    Joined:
    Feb 9, 2002
    Messages:
    4,733
    Likes Received:
    81
    Location:
    California

    What limit? Are you saying that if I define a set S_k = {k} and let k go to infinity, it isn't countable? Or are you saying let S_k = {all n < log_2(k)} (length in bits) is not countable? Can you actually produce a construction for the set that you are claiming isn't countable?

    BTW, there is no program of infinite length, unlike real numbers. Programs can approach arbitrarily long length, but can't reach it. It makes no sense to speak of *two* infinitely long programs, unlike say, two irrational numbers. That's what I mean "allow lengths to approach infinity" The lengths can get arbitrarily big, that is, for any program N, there is a program N+1 (the successor) which is bigger.
     
  9. Fred

    Newcomer

    Joined:
    Feb 18, 2002
    Messages:
    210
    Likes Received:
    15
    Im not so sure about that. There could exists programs that invoke themselves recursively an infinite amount of time, in an manner that is no longer directly mappable to the integers (they would map themselves to the reals actually)

    It depends on if we're allowed to enumerate recursion. I'm not a pro on computer set theory formalisms, as I don't know the basic assumptions we're working under. Probably little turing machines.

    Also, If in reality theres only a set amount of primitive instructions (say an algebra of instructions), there exists most certainly sets of programs which cannot be included in the language of the algebra, unless you approximate them to within a compact space.
     
  10. OpenGL guy

    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    2,357
    Likes Received:
    28
    Define Sn = {all integers of length n or less}. What's the limit set of Sn? I'll give you a hint: lim (n -> infinity) n is an element of this limit set.

    Take ClassX as defined by arjan, but instead of mapping the programs to the integers as strings of 1's and 0's, map them to the rationals as decimals by adding a decimal point before your string of 1's and 0's and call this ClassY. There is clearly a 1-1 mapping between ClassX and ClassY. Now, take limit as n goes to infinity, ClassY goes to the real numbers.

    When you say "let n tend to infinity" that is a limit. If you want to talk about an infinite union, then say that because it's not the same thing.

    The original union makes no sense when compared to reality: Eventually n will be larger than all the atoms in the universe, so you can't even store such a program.

    Let me give a different example. Let Xn = { n-tuples composed of As and Bs}. Thus, X1 = {A, B}, X2 = {AA, AB, BA, BB}, etc. The limit of Xn as n goes to infinity contains strings of infinite length.

    Now, replace A with "0" and B with "1". You get strings of 0s and 1s of infinite length. Note: These are not integers, but that's ok because limit points can be outside the set in question. In fact, these aren't real numbers, but they can make sense as a program:
    mad
    mad
    mad
    ...

    Doesn't that make sense? Who cares that it's never going to finish? We aren't talking about reality here.

    Now consider:
    lrp
    lrp
    lrp
    ...

    Two distinct infinitely long programs.

    This is why I prefer to use ClassY instead of ClassX: The limit set is easily understood to be the real numbers. In fact, I think taking the limit of ClassX makes little sense, however, I can put an measure on these infinite strings that makes sense.

    Anyway, here's a link regarding my above construction:
    http://merlin.capcollege.bc.ca/rbrewste/math224/ass2soln.pdf
     
  11. Oats

    Newcomer

    Joined:
    Feb 11, 2002
    Messages:
    37
    Likes Received:
    0
    :roll: :roll: :roll: :roll: :roll:
     
  12. arjan de lumens

    Veteran

    Joined:
    Feb 10, 2002
    Messages:
    1,274
    Likes Received:
    50
    Location:
    gjethus, Norway
    A program can have a finite size, yet have infinite running time, like this rather useless C program:

    int main() { return main(); }

    The mappings we seem to be discussing are mappings between the program source or object code and the integers, rather than between program invocations and the integers.

    And - offtopic? Yes indeed :-?
     
  13. Fred

    Newcomer

    Joined:
    Feb 18, 2002
    Messages:
    210
    Likes Received:
    15
    Right there the program has a recursive call that is enumerated by an instruction.

    lets say the program is

    start (main)
    printf('hello')
    call (main)
    end

    If we are talking about something like a turing machine, that program is reducible to an infinitely countable set. (let hello = 1, fundamental sourcecode = 1111111....) unless you make a new instruction that defines an infinite loop, then its say (12, 2= loop). Thats where it gets hazy in my mind, without specifying a number of fundamental instructions the actual length of the program is secondary.

    However if we are talking only about pure length, with an infinite amount of instructions available, then I still side with OGL. For the reasons he gave.

    Either way really, its uncountable.
     
  14. arjan de lumens

    Veteran

    Joined:
    Feb 10, 2002
    Messages:
    1,274
    Likes Received:
    50
    Location:
    gjethus, Norway
    A program that runs forever essentially corresponds to a turing machine that is unable to halt. If the langauge we use to define a program is turing-complete (which the PS2.0 shader language isn't), we can always code an infinite loop with a finite number of states/instructions/commands. Going back to ClassX versus ClassNull, any program with an infinite loop is a member of ClassNull.

    The set of all turing machines is countable, as far as I can see. The set of all inifinite-length "programs" is, of course uncountable, though, but only as long as these "programs" are not in any way expressible in a finite number of symbols (otherwise you just count the expressions).
     
  15. Basic

    Regular

    Joined:
    Feb 8, 2002
    Messages:
    846
    Likes Received:
    13
    Location:
    Linköping, Sweden
    Key point for those who want to untie the knot:

    What is the definition of "lim An as n->inf", especially when it's the limit of a series of sets. (Be careful with this one.)

    Is there a difference between
    "There can exist limit points to a set E outside E."
    and
    "The union of a (countable) sequence of sets En can contain a point that is outside all of En."
     
  16. Fred

    Newcomer

    Joined:
    Feb 18, 2002
    Messages:
    210
    Likes Received:
    15
    Every neighborhood of the limit point P should contain a point Q != P such that q is still in the set.

    Ie every neighborhood of P should contain infinitely many points of the set.
     
  17. OpenGL guy

    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    2,357
    Likes Received:
    28
    Easy: It's the limit points of the An's. Or, expressed another way, if there is a convergent sequence of xn's such that xn is an element of An, then the limit point of this sequence is in lim An.
    A union B = set of all x such that x is in either A or B. An element of an infinite union must be in one of the sets being unioned.

    And there can certainly be limit points to a set outside the set itself. The limit points of the rational numbers is the whole real line, which contains irrational numbers, for example. Or take X = {1, 1/2, 1/3, 1/4, ...}. 0 is a limit point of this set.
     
  18. Basic

    Regular

    Joined:
    Feb 8, 2002
    Messages:
    846
    Likes Received:
    13
    Location:
    Linköping, Sweden
    Maybe I should have ploughed through more of the posts, ... but naaah. (I noticed after I posted that you already had addresed some of it, but your last post was clearer to me.)


    The point I wanted to get at was that you were thinking of ClassX as two different things.
    But given the idea you had about what ClassX is, you all made a correct analysis of it.


    here
    That's an union of an infinite amount of countable sets. Not a limit set. The union is countable. It does not contain the limit points. Elements can be arbitrarily large, but not be infinite.

    If you instead define ClassUN as the union of Class1,...ClassN. And then define ClassZ as lim (N->inf) ClassUN, with the definition of limit you said above. Then you'll get an uncountable set.
    But that wasn't what arjan said (at least not in the post I read).

    I think ClassX is a more interesting class than ClassZ.


    The first question I asked wasn't a "have you got this right"-check. It was for the reason that I don't remember seeing a definition of it in any book. (It was a long time since I read any math though.) So I tried to think of the normal definition. That would need a distance function between two sets. First thought was the Lebesgue measure, but it didn't quite cut it.

    So I thought about of the definition of lim (n->inf) f(n). (For every epsilon there is...) And got to this:

    Ainf = lim (n->inf) An
    <=>
    For every point x in Ainf, there is an N such that x is in An for all n>=N.

    This definition (as opposed to the definition you gave) would have the property that:
    lim (n->inf) union (i=1...n) Ai = union (i=1...inf) Ai

    Is the definition you gave established as THE definition? And in that case, can you give the reason why we'd want a definition that includes limit points of the set. It doesn't have to be the same kind of "limit" in "limit points of the sequence of sets" and "limit of the sequence of sets".
     
  19. Althornin

    Althornin Senior Lurker
    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    1,326
    Likes Received:
    5
    Only if the set is open... (or rather, NOT closed)
     
  20. OpenGL guy

    Veteran

    Joined:
    Feb 6, 2002
    Messages:
    2,357
    Likes Received:
    28
    I did say "can", didn't I? I didn't say "must exist". "can" implies "possibly", not "must be".
     
Loading...

Share This Page

  • About Us

    Beyond3D has been around for over a decade and prides itself on being the best place on the web for in-depth, technically-driven discussion and analysis of 3D graphics hardware. If you love pixels and transistors, you've come to the right place!

    Beyond3D is proudly published by GPU Tools Ltd.
Loading...