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...
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)").
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".
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.
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.
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.
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?
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.
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.
#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?
Well.. close enough :D
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.
As in vault topic :D
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.
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):
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.
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.
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)".)
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.
-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?
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?
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).
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!
r = 1/(1/sin(pi/n)-1)*R
r - smal radius
R - big radius
n - count of small circles
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.
Just stretch a bunch of circles touching each other and you have a bunch of ellipses touching each other.