0
$\begingroup$

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names such as Depth-First Search, or Breadth-First Search or A* Search, etc.

However, I have the following game that I would like to input to my computer. The game is simple, you pick ten numbers. If all ten of the numbers are the number 1, then you win.

However, there are an infinite amount of decisions that the computer could take even with picking the first number. It could choose 8, or pi, or -3, etc.

Thus, even if I use something like A* and program in a heuristic such that it's obvious to the computer that choosing 1 is the best option, the computer still wont have enough memory to evaluate the heuristic on other the other options and make an informed decision.

How can computers handle cases like this? What sort of data structures are used when dealing with situations where there is not enough memory to hold all of the data, but there is enough to hold the relevant data at any given time?

(Compressed sparse data structures come to mind, but I'm not exactly sure how they can be used here.)

Improve this question
$\endgroup$
  • $\begingroup$ If your domain of numbers is infinite and you pick numbers according to a uniform distribution, then the probability of choosing 1 (or any one of them, in fact) is exactly zero. Hence, you can only win if you play infinitely many times... $\endgroup$ – dkaeae Jan 9 '19 at 8:45
  • $\begingroup$ Also, (real-world) computers only have finite memory, so there is no way of accounting for infinitely many numbers (without risking running out of memory). $\endgroup$ – dkaeae Jan 9 '19 at 8:47
  • $\begingroup$ Yes, I’m aware of these issues. Somehow though, human brains are able to understand the concept of an infinite amount of choices while still just paying attention to the ones that are relevant. I think there may be a sort of data structure or object I could create that would do something similar. $\endgroup$ – Pro Q Jan 10 '19 at 14:09
  • $\begingroup$ Human brains are also capable of solving the halting problem—TMs (and computers) not. $\endgroup$ – dkaeae Jan 10 '19 at 14:11
  • $\begingroup$ We do not know if human brains are also capable of solving the halting problem $\endgroup$ – Pro Q Jan 10 '19 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.