1

If we're given a computer program, how can I prove that there is a greater number of points in the domain than the number of paths? The question I am asked is "Which is larger? The number of paths in a program or the number of points in its domain?"

This is what I have so far, but I feel I'm not expressing my thoughts properly: "A domain has to have at least one path, but a domain can have more than one path or more than one domain. There can be more domains than paths, if each domain uses a path that routes through the same routine or, in other words, through a loop. Otherwise, there would be more points than paths in a domain."

Just got a response back from him: "If there is a loop in the program, the same sequence of nodes in the graph may be visited numerous times. The number of points in the domain has nothing to do with the number of nodes in the program graph. It has to do with the values of the inputs to the program that drive it through the paths.

In your diagram, there are five ways to get from the top of the loop to the bottom. Each path executes a distinct sequence of functions. When there is a loop back, the sequence of functions that is executed by the program gets longer. If you think about all of the different sequences of functions that could be executed in the program through repeated looping, this is a big number, as you have correctly shown.

The domain refers to a set of data values that are inputs to the program. When you run the program, you present it with a collection of inputs. The program processes these inputs and produces outputs. You are correct to model the entire program as a mathematical function. This is why the inputs are called the domain (as in domain and range of a function in set theory). Each point in the domain represents a different distinct collection of input values. The entire set of different collections of inputs is the domain of the funtion. Each unique collection of inputs (i.e., each point in the domain) maps to some particular collection of outputs (or point in the range). The number of points in the domain is a big number.

The flow graph of the program has nothing to do with the domain or range.

So the question is this: if you count the number of different unique collections of inputs (i.e, the cardinality of the domain), is this bigger or smaller than the number of distinct paths through the program? We are comparing very large numbers to very large numbers. But one of them is clearly bigger, and it can be proved."

biohack
  • 111
  • 2
  • 5
    These are not correct mathematics uses of these words. You should give, in any case, the book title, author(s), and page number(s) for what you are trying to describe. – Will Jagy Aug 12 '13 at 22:25
  • This was a question asked by a software engineering professor in class. No textbook used in his course. His question was as such "Which is larger? The number of paths in a program or the number of points in its domain?". I'm thinking the program as a mathematical function, and domain as mapping inputs to outputs. – biohack Aug 12 '13 at 22:28
  • Then how did your professor define "paths" and "domains"? – Cameron Buie Aug 12 '13 at 22:31
  • Would a program that prints "Hello World" count as having one path and one domain, or does it have no domain as there are no inputs? There is some terminology here that has to be clarified in order to give a useful answer. – JB King Aug 12 '13 at 22:33
  • 1
    This is a diagram I created to help explain my case. http://i.imgur.com/Pr3iTTt.png?1 There are five paths. If the program loops 20 times, then the total number of possible paths would be 5^20 + 5^19 + 5^18 ... 5^1 = ~10^14. – biohack Aug 12 '13 at 22:38
  • @JBKing yes, that is one possible path. If the input is greater than 1, then it would print another message and that's another path. That is how I'm interpreting his terminology. – biohack Aug 12 '13 at 22:39
  • 1
    While it isn't hard to count execution paths within a program, I'm still at a loss to understand how you count the domains? If a program takes no input, is that an empty domain or one because the output of the program is fixed regardless of input? I'm trying to clarify how you count domains since if one writes a program to output the character entered could well have more domains as there are lots of various strings one could enter, while on the flip side one could write the program that takes no input and uses random numbers to generate multiple paths that works the other way. – JB King Aug 12 '13 at 22:45
  • I apologize I made that assumption. I have edited my original post to include clarification that the professor made via email. – biohack Aug 12 '13 at 22:46
  • @JBKing I refer domain as the set of inputs fed into the program. – biohack Aug 12 '13 at 22:49
  • If a domain can have more than one domain, I'm missing how this doesn't make for a loophole that collapses this down to the domains will be greater as one could just take power sets recursively to build up a super set of any arbitrary size. This can grow somewhat unbounded while the paths in the program are somewhat fixed given the issues of the Halting problem. – JB King Aug 12 '13 at 22:51
  • What is the model of computation? How is input presented to the program? It's common to consider things like finite-state machines, Turing machines, etc. These tend to deal with things like strings of symbols. You haven't said what the input could look like, or what the program could look like.... – dfeuer Aug 12 '13 at 22:53
  • The image Steve linked in the second comment shows something similar to a finite-state machine. – JB King Aug 12 '13 at 22:57
  • If a program takes no input, is this a domain or no domain? If this is treated as no domain then there can be an execution path without input that gives one more path than domains. However, if that counts as a domain, then things can get wonky as one could always try to create other domains even though the input is irrelevant for the program. While this is intended to be a simple exercise, there are some special cases that can make this a bit tricky unless one defines things to rule those out. – JB King Aug 12 '13 at 23:07
  • @dfeuer he only mentioned this question in passing and did not give any context to the model it reflects though I'm interpreting it as a finite state machine. – biohack Aug 12 '13 at 23:08

1 Answers1

1

I think the answer is probably intended to come from the rather trite observation that each possible input results in some execution path, while two different inputs could result in the same execution path. Therefore there are at least as many points in the input domain as there are execution paths.

Rob Arthan
  • 48,577
  • I think so too, as long as the machine behaves deterministically. But without the details, we can't prove anything. – dfeuer Aug 12 '13 at 23:04