1

It is a common programmer hobby to write programs which accomplish a task in 1 line of source code. But that is a bit trivial: I can take 1 000 000 lines of code, delete all the line breaks, and voila! 1 line!

So to make things interesting, we can count statements. For a C-style language, a simple of way of counting statements is counting semicolons: So nesting a million if-elses is fine.

Say you've got a program P with n statements. It goes through a sequence of states (variable values) s (where s is a vector) and produces output x. We can pose two questions:

  1. Can a program with fewer than n statements produce output x?
  2. Can a program with fewer than n statements go through some subset of s?

Immediately, some things become obvious. Take the following program:

int sum = a+b;
float mean = sum/2.0;
return mean;

We can refactor (or should I say "defactor") this into a one liner:

return (a+b)/2.0;

Can every program be defactored to one line? Take this program:

string x = "";
for (int i = 0; i<a; i++)   // Should these semicolons count?
{
    x = x + ".";
}
return x;

It's a bit more challenging.

The question can be answered exhaustively by trying every possible program with less than n statements, a number which is finite (theoretically you could have constants with infinitely many possible values, but no real language has infinite memory to store them or infinite disk space to accommodate the source code).

However:

A. Is it possible to prove for a program P which produces x (perhaps through s) with n statements that no Q which can do it in m statements can be found (in an efficient manner)?

B. Can the minimum n be found (in an efficient manner)?

C. Is minimum n guaranteed to be 1?

You can assume any language you want, although real languages would be more interesting. Please provide a definition of a "statement" in your language if your language is unusual.

I have assumed imperative languages, but adaptations of the problem to functional languages are welcome.

There is a trivial solution: For any P, run P and record x. Now write a program Q which simply prints x. For programs with input, make a very long if-else with each input mapped to a correct output.

This solution is unsatisfactory, although I'm not entirely sure why. Firstly, for infinite possible inputs it's impossible (but I already covered my ass by saying real programs are finite, so we can say real input is finite). Second, it only technically passes through a subset of s: Namely the empty set. Third, it's really anticlimactic.

Any help with defining away this little clever trick is also appreciated.

PS: For whatever my word is worth, this isn't homework. I simply got curious about the problem and tried to phrase it as clearly as I could. Of course, I would still say that if it was homework, so...

4

1 回答 1

3

由于语句的概念是特定于语言的，因此在某些语言中，每个程序都可以编写为单个语句或表达式。地狱，甚至有些语言必须将每个程序编写为单个表达式。

也就是说，假设一种语言不是这种情况（并且肯定存在这样的语言），找到解决给定问题的最少语句的问题既不在 P 也不在 NP 中——这是不可判定的。

这个问题可以通过使用少于 n 个语句的每个可能的程序来详尽地回答，这个数是有限的

由于其中一些程序不会终止，并且不可能知道哪些程序会终止（停止问题），因此这是行不通的。

此外，在大多数语言中，少于 n 条语句的程序数量也不是有限的。例如，return foo + bar + ... + baz;在大多数语言中，有无数种形式的陈述。

A. 是否有可能证明一个程序 P 用 n 个语句产生 x（可能通过 s），不能（以一种有效的方式）在 m 个语句中找到可以做到这一点的 Q？

（我假设你在m < n这里忘记了，否则这个问题没有意义。）

不，根本无法证明。

B. 是否可以（以有效的方式）找到最小值 n？

不，根本找不到。

C. 最小 n 是否保证为 1？

正如我在开始时所说，这取决于语言，出于上述问题的目的，我假设一种语言的答案是否定的。

于 2012-09-01T09:44:53.090 回答