1

Edit: There has to be an adjustment to my question as the number of permutations far exceeds 1 trillion which would lead to the main program doing way more than 1 trillion operations. Therefore, the number of operations allowed for the programs will be chosen such that they exceed the number of operations the main program will take to create all those permutations and compare the stored results in memory. Keep this in mind while reading the question.

Is following task achievable?

Find the first program which is larger than 1 million in symbol size which produces a NEW sequence of symbols as output within less than a trillion operations. New sequence as in not having been generated by any other program with less than a million symbols in size and within a trillion operations.

One could consider writing a main program which creates all permutations of symbols valid to our programming language up to a million symbols in length.

Store those permutations as source code to a program and then run each of the code in a separate thread up to a trillion operations.

If a program returns with a finite sequence of symbols as output within 1 trillion operations, store that output in memory.

When all programs with less than a million symbols in size finished, the main program would then generate permutations of symbols with more than a million symbols in size and run a trillion operations on them.

Every such program which would produce a finite sequence of symbols as output within 1 trillion operations would have its output compared to the outputs stored in memory.

If the output is new, hence not stored in memory, one would think that we completed our task. We found the first program that is more than 1 million symbols in size and which produces a new finite sequence of symbols within 1 trillion operations.

But we did not! Our main program which is much smaller in size can simply output that same sequence, as it is the program checking each output and compares it to those stored in memory.

This might be closely related to berry's paradox.

However, this program could actually be written and if we had fast enough computers to actually perform all those operations in the future, the program should give us an output at some point. But seemingly the output would be wrong as it leads to the contradiction.

Does this mean that there exist no first program with more than a million symbols in length that outputs a new first sequence within 1 trillion operations? How can such a program not exist at all?

pZombie
  • 111
  • You do not necessarily have a contradiction. The main program might need more than $1$ trillion operations to output the "new" sequence. – Peter Jan 30 '19 at 21:16
  • What you also should clarify : What if a program does not output a single number within $1$ trillion operations ? – Peter Jan 30 '19 at 21:19
  • @Peter Yes, that is correct which is why i edited my question. I guess you did not check the edited version. In the edited version i request the number of operation for each program is to be chosen such that it exceeds the number of operations the main program requires to complete. Since the main program is very predictable, the minimum number of operations it will require to complete should not be hard to predict. – pZombie Jan 30 '19 at 21:19
  • @Peter The symbols a program outputs do not need to be translated into a number. We can regard them as just a sequence of symbols. Either a program outputs a sequence of symbols within a given number of operations or it does not. You can of course use some encoding to translate any sequence of symbols into some number. A single number. – pZombie Jan 30 '19 at 21:22
  • not exactly following this but it seems designed to create a possible contradiction but none seems to be there. it would be helpful to formulate this in terms of Turing machines. another aspect that maybe is being missed here: Turing machines take increasing time to "access" larger memory due to moving the tape head costing 1 step. yes one might be able to achieve contradictions if one postulates physically impossible machines... another way to think about it is that machines with 0 memory access time or nonzero access time are both valid theoretically but a mixing of the ideas may not be. – vzn Jan 31 '19 at 01:54
  • @vzn The main idea is that there have to be sequences of symbols which require a program that is larger than 1 million symbols in size in order to be produced as output within less than a fixed amount of cycles. If such sequences exist, then there has to be a first such sequence when going through all permutations. The main program is designed to find the first such program which produces a new sequence and could also be designed to print out the program's output as a final step. But the main program is way less than a million symbols. – pZombie Jan 31 '19 at 04:53
  • @vzn Or simply ask yourself if you can complete the task. Can you write a program which discovers the first sequence of symbols that requires a program that is greater than 1 million symbols in size (and finishes in a fixed amount of cycles)? If yes, show us how. If you cannot do it then does it mean that such a sequence does not exist? If there is no such first sequence which requires a program of at least 1 million+ symbols then how can there be a 2nd, 3rd etc... how can there be any at all? – pZombie Jan 31 '19 at 05:04
  • this problem is somewhat similar, Busy Beaver https://en.wikipedia.org/wiki/Busy_beaver – vzn Jan 31 '19 at 05:24
  • @vzn Part of the solution might be that the main program would inevitably generate itself and since one of the requirements of my now edited version is that the number of operations/cycles for each program needs to be at least the amount of cycles the main program will take to complete, the clone of the main program generated by the main program will also run the same amount of operations meaning the clone will also generate a clone of itself... here is where i get lost. Maybe someone smarter than me can shed some light. – pZombie Jan 31 '19 at 05:47
  • @pZombie The last point is exactly what always confused me (and still confuses) about the proof of the impossibility to solve the halting problem. Here, we do not have this problem because we limit the number of possible steps. Nevertheless, I am still not sure whether a machine outputs something BEFORE halting ( a turing machine cannot do that ). We should clarify this first. Do you stop every program when the $1$ trillion operations are done ? And what is the output then ? – Peter Jan 31 '19 at 09:59
  • @pZombie What we could do however that we look at the tape after the turing machine has done $1$ trillion steps (if it did not halt before). In this case, I think we have no contradiction because the turing machine checking all the programs will probably not be able to do the job within the given $1$ trillion operations. – Peter Jan 31 '19 at 10:05
  • @Peter As i already replied earlier to you, the question was edited to change this into having the programs perform a minimum of operations which is greater than the operations the main program performs. One capable might want to translate this into a turing machine problem. In my simplified version it is just a normal program in a given programming language for which there are many way to define the output. We could define it as whatever the program prints to the screen or stores in a certain memory address. If a program does not halt and has no output the main program just dismisses it. – pZombie Jan 31 '19 at 15:23
  • @Peter What i am asking myself is, if one can simply consider the operations the subprograms, the main program creates, as independent or if they have to be considered part of the operations to the main program. If one can consider them independent, then what about the clone of itself the main program would generate inevitably which it turn would create its own clone? If the clone and the clone of the clone operations are counted towards a total, we could finish the counting process. But if each clone of the clone of the clone etc.. would get its own count, then this is an infinite process. – pZombie Jan 31 '19 at 15:29
  • @Peter But if we choose to include the operations of the subprograms to the main and use that method towards counting the total operations, then of course the question would not make sense as the main program would ALWAYS perform more operations vs its subprograms. If we choose the other method of counting, where each subprogram is independent of the main, then as stated above, we would end up with a never ending counting process in some cases ,as is the case with the clones of the main program. – pZombie Jan 31 '19 at 15:35
  • see also "berry paradox relationship with kolmogorov complexity" https://en.wikipedia.org/wiki/Berry_paradox#Relationship_with_Kolmogorov_complexity – vzn Jan 31 '19 at 16:45
  • The more i think about it, the more certain i am that my mistake was in not including the operations of the programs the main programs creates to the total operations of the main program, since the main program makes use of their output in order to compare the found new sequence, they are in a sense part of the main program when not run independently and the main relies on their output. Therefore it is not possible for the main program to run an equal number of operations when the other programs are to stop whenever the new sequence is found, Or so it appears to me. – pZombie Feb 01 '19 at 13:43

0 Answers0