Body: <p>I am pondering on the question in the title. As a human being, somehow I can sort a random sequence of numbers from 1 to <span class="math-container">$ 2^{2^{512}} $</span>  in our universe in infinite time (But I am not sure.). Can an ML model do that in our universe if it is provided with infinite time? There is no restriction on how the learning algorithm is supposed to learn how to sort. (Be careful, even <span class="math-container">$ 2^{512} $</span> is bigger than the number of atoms in the universe. Therefore you will have limited memory.)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-06T03:11:25.103Z
Comments.Text: Are you basically asking whether a ML algorithm can learn to sort? What's the point of the range if you give the algorithm an infinite amount of time, can you elaborate a bit on that?
Comments.UserDisplayName: SpiderRico
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-06T03:26:24.573Z
Comments.Text: @SpiderRico The point is that the number is very huge which cannot be represented by bits. I try to compare human cognition and ML models. It seems (not sure) that the computer cannot sort such big numbers because, after a point, the numbers cannot be represented even if you use all atoms in the universe to represent numbers. Can a human solve the problem without time limitation?
Comments.UserDisplayName: verdery
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-06T03:55:05.510Z
Comments.Text: So you assume a memory limit then? Isn't then the question essentially boils down to whether we can store such a number in memory or not? I just can't see the ML part of the question here.
Comments.UserDisplayName: SpiderRico
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-06T04:06:27.460Z
Comments.Text: The question is related to machine learning because I'm asking if an ML algorithm could theoretically learn how to sort any sequence of numbers (i.e. if it could learn some sorting algorithm).
Comments.UserDisplayName: verdery
Tags: <machine-learning><computational-learning-theory><learning-algorithms>
Title: Can an ML model sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time?
UserDisplayName: verdery
ThreadText: # Can an ML model sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time?
  
  (Asked by: username_0 on 2021-02-05)
  
  I am pondering on the question in the title. As a human being, somehow I can sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time (But I am not sure.). Can an ML model do that in our universe if it is provided with infinite time? There is no restriction on how the learning algorithm is supposed to learn how to sort. (Be careful, even $ 2^{512} $ is bigger than the number of atoms in the universe. Therefore you will have limited memory.)
  
  **Tags:** machine-learning, computational-learning-theory, learning-algorithms
  
  > **Comments:**
  > **username_1**: Are you basically asking whether a ML algorithm can learn to sort? What's the point of the range if you give the algorithm an infinite amount of time, can you elaborate a bit on that?  
  > **username_0**: @username_1 The point is that the number is very huge which cannot be represented by bits. I try to compare human cognition and ML models. It seems (not sure) that the computer cannot sort such big numbers because, after a point, the numbers cannot be represented even if you use all atoms in the universe to represent numbers. Can a human solve the problem without time limitation?  
  > **username_1**: So you assume a memory limit then? Isn't then the question essentially boils down to whether we can store such a number in memory or not? I just can't see the ML part of the question here.  
  > **username_0**: The question is related to machine learning because I'm asking if an ML algorithm could theoretically learn how to sort any sequence of numbers (i.e. if it could learn some sorting algorithm).  
  
  ---
  
  ## 0 answers
  
  