Amaraticando
It/Its
Editor, Player (159)
Joined: 1/10/2012
Posts: 673
Location: Brazil
Warp wrote:
"What is the largest integer that can be computed by a terminating C++ program of at most 1000 characters?" The condition that the program must terminate actually puts an upper limit to how big the computer number can be. Since the program has a limited size, the computed number also must have a limited size. Thus the core question is whether this problem is unsolvable or just very hard.
Since there're only finite C++ programs with 1000 characters or less, the problem can be reduced to: can we decide if a C++ program will ever halt (with null input)? I can think of a bunch of problems for which the answer is unknown. For instance, consider the following pseudocode:
Language: pseudocode

function is_perfect_number(int n) blablabla return bool_perfect_number // true if n is a perfect number, false otherwise end int n = 1; while true do print(n); if is_perfect_number(n) == true then break end n = n + 2; end
Since no one knows whether some odd perfect number exists, we don't know if this program will stop. Of course there's a difference between unknowledge and undecidability. So, is this problem decidable? Possibly, only if there's no odd perfect number. I have to investigate that...
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Bobo the King wrote:
I think you're right, however, that we could simply list all programs with 1000 or fewer characters and analyze whether they halt or not. I see no reason why that shouldn't be possible.
Actually, I'm not sure it's that simple. I think it depends on whether the program has an unlimited amount of memory (and addressing space) available to it. I suppose the original problem was insufficiently defined because it didn't specify whether the program has unlimited memory addressing or not. I'd say that with this kind of problems one can assume that by default the amount of memory is unlimited (and the program can address all of it). So if we make that assumption, I wouldn't be so hasty to proclaim that the halting problem is solvable even if we limit the length of the program's source code. What the limit on the length of the program's source code does, however, is that it limits the amount of possible ending conditions (because the ending condition must have been somehow expressed in the source code, no matter how convoluted and complex that condition might be). But (and that's a big but), if there is indeed an unsolvable halting problem, this might mean that it's likewise impossible to determine the answer to the original problem (ie. "what's the smallest positive integer that can't be computed") or its converse (ie. "what's the largest integer that can be computed (the program must terminate)").
Player (146)
Joined: 7/16/2009
Posts: 686
Warp wrote:
So if we make that assumption, I wouldn't be so hasty to proclaim that the halting problem is solvable even if we limit the length of the program's source code.
Again, this is not the halting problem. Amaraticando's post perfectly illustrates the point: his given program might halt. It might not. We don't know yet, as someone has yet to (dis)prove the existence of odd perfect numbers. But it is possible to know it, which means we can determine whether the program will halt. The halting problem states that there is no algorithm that correctly determines whether a program will halt, not that humans are incapable of proving it for any arbitrary program. It's also important that the halting program involves input, which this problem does not. That means the "problem space" is finite (all C++ programs with 1000 char length), rather than infinite(all C++ programs with 1000 char length * all possible input). Bobo the King: algorithms take input and turn it to output, human minds give meaning to the input. While there exists languages of proof that allow for algorithmic checking of correctness, these are incomplete, and the whole notion of a proof rests on the human mind interpreting it. If you dig deep enough, you will always reach a point in logic where something is true simply because people agree it is, where there is no longer any underlying logic. This is where algorithms "fail".
HHS
Active player (286)
Joined: 10/8/2006
Posts: 356
Warp wrote:
Thus the core question is whether this problem is unsolvable or just very hard.
This problem has a trivial solution. Simply write the shortest possible program that does the following: - Clear all of the computer's memory - Output the digit 9 - If the program is in ROM, output more 9's until you run out of ROM space. This is easily accomplished with templates while staying well under the 1000 character limit. - Use all of the computer's memory as a giant counter, and repeat the above until the counter rolls over.
Amaraticando
It/Its
Editor, Player (159)
Joined: 1/10/2012
Posts: 673
Location: Brazil
HHS: this kind of problem always assumes that the memory is infinite. Therefore, your program would never stop and is not suitable.
Player (146)
Joined: 7/16/2009
Posts: 686
Even if we didn't make the assumption about infinite memory, you're still missing a vital point: it's not about "how high a number can I output", but about the smallest number that you cannot.
Player (98)
Joined: 12/12/2013
Posts: 379
Location: Russia
I don't see what is point to think about it. You can output any decimal number from 0 to ~1806 digits. Just put string in code and decode it from base64 for example. As far as 10^1806 - is not imaginable by me, I don't see any sense.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
r57shell wrote:
I don't see what is point to think about it. You can output any decimal number from 0 to ~1806 digits.
I don't really understand what you are trying to say. You can certainly output a lot more (consecutive) numbers than that with a (terminating) C++ program of 1000 characters or less, so the answer to both problems would be enormously larger than that. Either way (and once again), my question was not what the numbers are, but the nature of the problem itself: Is it unsolvable or just very hard?
Player (36)
Joined: 9/11/2004
Posts: 2630
Warp wrote:
One could naively think "it's not unsolvable; simply go through every possible valid C++ program of 1000 characters or less, and for each one see which numbers it outputs, if any". However, that method might not be usable because you may encounter the halting problem: You cannot know if a given program will ever halt.
This sounds related to the busy beaver function. https://en.wikipedia.org/wiki/Busy_beaver
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Tub
Joined: 6/25/2005
Posts: 1377
Scepheo wrote:
It's also important that the halting program involves input, which this problem does not. That means the "problem space" is finite (all C++ programs with 1000 char length), rather than infinite(all C++ programs with 1000 char length * all possible input).
And yet, deciding whether a program terminates can be very difficult even for a fixed program with fixed input. OmnipotentEntity has finally linked the very relevant busy beaver numbers. Read that article! Read it again! It's important to note that even with extensive research, the exact value of BB(5) is not known - that is, even for turing machines with exactly 5 states and no input, we have not managed to determine for all of them whether they terminate. Considering how fast BB numbers grow, for a 1000 char C++ program, I'm pretty sure the largest possible output is so large that it is impossible to contain its decimal representation within the observable universe.
m00
Tub
Joined: 6/25/2005
Posts: 1377
It's been a slow evening, so I wrote a small C program to simulate a turing machine. It simulates the current busiest beaver with 5 states, which terminates after 47.176.869 steps.
 A0  A1   B0  B1   C0  C1   D0  D1   E0  E1  sigma(M)    s(M)
1RB 1LC  1RC 1RB  1RD 0LE  1LA 1LD  1RH 0LA    4098   47,176,870
#define S 5
#define TAPESIZE 0xffffffff
#include <cstdio>
typedef long long int LONG;
char nextstate[S][2] = {
	{ 'B', 'C' },
	{ 'C', 'B' },
	{ 'D', 'E' },
	{ 'A', 'D' },
	{ 'H', 'A' }
};
bool symbol[S][2] = {
	{ 1, 1 },
	{ 1, 1 },
	{ 1, 0 },
	{ 1, 1 },
	{ 1, 0 }
};
char movement[S][2] = {
	{ +1, -1 },
	{ +1, +1 },
	{ +1, -1 },
	{ -1, -1 },
	{ +1, -1 }
};
int main() {
	LONG position = 0;
	char state = 0;
	bool *tape = new bool[TAPESIZE]; // interleaved: 0, -1, 1, -2, 2, ...
	size_t i=0;
	while (true) {
		LONG idx = position >= 0 ? 2 * position : -2 * position - 1;
		if (idx > TAPESIZE) {
			printf("Machine exceeded tape size at step %lu\n", i);
			return 5;
		}
		bool read = tape[idx];
		tape[idx] = symbol[state][read];
		position += movement[state][read];
		char s = nextstate[state][read];
		if (s == 'H') {
			printf("Terminated after %lu steps\n", i);
			return 0;
		}
		state = s - 'A';
		i++;
	}
}
If we output a '9' each iteration, our output number would thus be 1047.176.869-1. It is well below 1000 chars, so we can change the TM to a 6-state machine without problems. The busiest beaver with 6 states iterates more than 7.4 × 1036534 times. If you output a digit each step, then the result will not fit into the observable universe, which only has somewhere in the ballpark of 1080 particles. Of course, neither will the virtual tape - and I've yet to see a C++ compiler supporting 64KB pointer arithmetics. Now feel free to obfuscate the code and figure out how much room is left to define the TM. How many states can we support? How big do you need the output number to be?
Bobo the King wrote:
To throw out a guess, perhaps one million or so digits.
Well.. close enough :D
m00
Player (146)
Joined: 7/16/2009
Posts: 686
Again, Tub, it's not about the largest number. It's about the smallest number you can't output.
Player (98)
Joined: 12/12/2013
Posts: 379
Location: Russia
Task about smallest number that you cannot output. even if you have all possible 256 characters in C++ program, you can reach maximum 256^1000 different possible outputs. And you'll get 256^1000 smallest that you can't output if and only if there is NO GAPS among all different outputs, and all programs is working, and all programs is terminating. So upper bound for answer for this task is 256^1000. and it's somewhere around 10^2408. Summary: lower bound is around 10^1806, and upper bound is 10^2408.
Warp wrote:
I don't really understand what you are trying to say.
As in vault topic :D
Player (146)
Joined: 7/16/2009
Posts: 686
Huh, r57shell's post reminds me of a pretty important aspect, even if you don't know whether a program terminates, if you can proof its (possible) result exceeds the upper limit, you can dismiss it. That actually sounds fairly doable. As only a fraction of those 256^1000 garbled messes are valid programs, the answer to this question might be a lot lower than I anticipated. EDIT: Interesting train of thought: for some amount of characters N, it "could" be possible to write a program that "solves" this question (by writing and running all programs of length N). However, as that program would also try itself (etcetera), it would never terminate. Even if it would, the fact that it would output the lowest "incomputable" number, means that number is, in fact, computable. As such, such a program can not exist.
Amaraticando
It/Its
Editor, Player (159)
Joined: 1/10/2012
Posts: 673
Location: Brazil
r57shell wrote:
even if you have all possible 256 characters in C++ program, you can reach maximum 256^1000 different possible outputs.
256^1000 is the number of possible strings. The vast majority of them won't compile correctly. I don't know what it has to do with the problem. For instance, let's suppose for the sake of the argument, that n = 10^(10^10)+1 is the smallest perfect odd number. The pseudocode that I wrote will print every number from 1 to n and then will halt. Tub and OmnipotentEntity are correct, this problem is related to the busy beaver. In that article, the Applications' content has a similar example and an explanation that I don't agree with (if I understood it well):
Wikipedia wrote:
Consider any conjecture that could be disproven via a counterexample among a countable number of cases (e.g. Goldbach's conjecture). Write a computer program that sequentially tests this conjecture for increasing values. In the case of Goldbach's conjecture, we would consider every even number ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on an n-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is not the sum of 2 primes in our example), it halts and notifies us. However, if the conjecture is true, then our program will never halt. (This program halts only if it finds a counterexample.) Now, this program is simulated by an n-state Turing machine, so if we know S(n) we can decide (in a finite amount of time) whether or not it will ever halt by simply running the machine that many steps. And if, after S(n) steps, the machine does not halt, we know that it never will and thus that there are no counterexamples to the given conjecture (i.e., no even numbers that are not the sum of two primes). This would prove the conjecture to be true.
Player (98)
Joined: 12/12/2013
Posts: 379
Location: Russia
Amaraticando wrote:
256^1000 is the number of possible strings.
Nope, it's number of different C++ programs that is possible. Assume that they all is correct, terminating, and has different output. Then you'll get 256^1000 different outputs. If you'll allow several numbers in output of one program, then you can write such program:
Language: c

for (int i=0; i<(1<<(1<<(1<<10))); ++i) print(i);
where you can put 1<< around 1000/4 times, and it's really very big number. I think you can make condition easier to make much bigger last number. something like *((((10)!)!)!)! (factorials) or put it into n and find n-th some rare kind of number, like perfect number, or n-th prime number (where to stop). Any way there is no sense in that big numbers.
Amaraticando
It/Its
Editor, Player (159)
Joined: 1/10/2012
Posts: 673
Location: Brazil
Several outputs are allowed, but not infinite ones. I will try to formulate the problem in another perspective. We know there're much less than 257^1000 programs with 1000 chars or less that prints a finite set of numbers and then stops. Those that print an infinite set (and therefore never halts) must be eliminated. For example: Program 1 outputs {1, 3, 7} ✔ Program 2 outputs {1, 2, 3, ..., 10^1000} ✔ Program 3 outputs {1, 2, 3, 4, ...} ✖ discarted Program 4 outputs {1, 2, ..., up to the smallest odd perfect number} ??? how the hell can we know if it will be discarted or not? . . . last Program N outputs {8} ✔ Where N < 257^1000. Let R be the union between all those sets. Then, R is finite and is not . Therefore, ℕ\R has a minimal element k. The problem is: can we build an algorithm that finds k? For sure, we can test all programs and add new elements to R. But if a program (like Program 4) lingers to end, how can we know if it ever will? AFAIK, that's the only part missing from the solution and I suspect there's no algorithm that fulfills this task. However, we can't say that based on the Halting Problem.
Player (98)
Joined: 12/12/2013
Posts: 379
Location: Russia
Amaraticando wrote:
Several outputs are allowed, but not infinite ones.
My example outputs finite set of numbers. Also, it wasn't you who state problem. It was Warp.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
I notice now that the original problem may have the ambiguity that it doesn't specify whether the program has to print only one number, or whether it's allowed to output an arbitrary amount of numbers (all of which are counted as being printed by said program, and thus count towards the solution to the posed problem). This makes a radical difference. If we require that the program only print one single number (even if it internally calculates any amount of them), it limits the result quite a lot (because only that one number will count in terms of the problem, but not any number smaller than that). If, however, we allow the program to output any amount of numbers, then such a program could print all the numbers from 0 to whichever large number it calculated. I suppose that for the problem to be more sensible, it would make more sense to require that it outputs only one number. (Of course internally it can calculate as many numbers as it wants, but it has to "mark" only one of them as the "result" of the calculations, which it outputs.) The alternative version of the problem (ie. what's the largest number that can be printed by such a program) obviously doesn't require that restriction (because we don't care if it prints smaller numbers as well). (Of course there are other technical aspects to the problem that have not been addressed. For example, are ints of unlimited size, or do they have a maximum size? If they are of unlimited size, then what does something like "unsigned(-1)" mean? Maybe the problem would be more sensible by replacing "C++" with a language that's completely agnostic to how big the variables can be, and has no trickery like "unsigned(-1)".)
Player (98)
Joined: 12/12/2013
Posts: 379
Location: Russia
In any language you can use library for big numbers. There are several libraries for that, or you may write one yourself. It's not so hard, I think 1000 symbols is enough, although we don't speak about performance.
Skilled player (1652)
Joined: 7/25/2007
Posts: 299
Location: UK
-Prove that a circle can be surrounded by exactly 6 others of its own radius. IE The above picture might actually be incomplete, there may be indistinguishable gaps in between each one; so prove it to make sure. -If surrounding the central circle with smaller ones, what radius would they need to be in order to have exactly 8 surrounding it instead?
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Those don't look like circles to me, but ellipses. Which gives me an idea for an additional question: Prove that an ellipse can be surrounded by 6 identical ellipses, each touching an adjacent ellipse only on one point. Bonus question: Can the ellipses have different orientations, and still fulfill the requirements?
Player (146)
Joined: 7/16/2009
Posts: 686
Flip: the centers of three equal-radii (r) circles make an equilateral triangle with side length 2r. As a corner of such a triangle is pi/3, exactly six fit in a full circle, giving you 6 points that are 2r away from the center and from each other, allowing for six circles of radius r to perfectly surround another circle of radius r. For any given number of circles n, it follows that the angle of the "triangle" will be 2*pi / n. This gives an isosceles triangle with a base of length 4r * sin(pi / n), giving surrounding circles with radius 2r * sin(pi / n).
Player (98)
Joined: 12/12/2013
Posts: 379
Location: Russia
Flip wrote:
-Prove that a circle can be surrounded by exactly 6 others of its own radius. IE The above picture might actually be incomplete, there may be indistinguishable gaps in between each one; so prove it to make sure.
Easy to prove. make regular triangle, make new ones on sides of that triange, and so on... then put circles with diameter of side, and center in vertices. Voila!
Flip wrote:
-If surrounding the central circle with smaller ones, what radius would they need to be in order to have exactly 8 surrounding it instead?
r = 1/(1/sin(pi/n)-1)*R r - smal radius R - big radius n - count of small circles
Editor
Joined: 11/3/2013
Posts: 506
The much harder question is to prove that such an arrangement is the most efficient way possible (ie there is no way to get a bunch of identical circles to cover a larger percentage of a plane). And, AFAIK, the case for spheres is still an open problem today - even though the answer seems pretty obvious, there's no elementary way of proving it.
Warp wrote:
Those don't look like circles to me, but ellipses. Which gives me an idea for an additional question: Prove that an ellipse can be surrounded by 6 identical ellipses, each touching an adjacent ellipse only on one point.
Just stretch a bunch of circles touching each other and you have a bunch of ellipses touching each other.