"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 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...Language: pseudocodefunction 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
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.
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.
Thus the core question is whether this problem is unsolvable or just very hard.
I don't see what is point to think about it. You can output any decimal number from 0 to ~1806 digits.
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.
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).
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++;
}
}To throw out a guess, perhaps one million or so digits.
I don't really understand what you are trying to say.
even if you have all possible 256 characters in C++ program, you can reach maximum 256^1000 different possible outputs.
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.
256^1000 is the number of possible strings.
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.Language: cfor (int i=0; i<(1<<(1<<(1<<10))); ++i) print(i);
Several outputs are allowed, but not infinite ones.
-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?-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.
