This subject is not the one you predicted
So I was talking about a short story that included time travel last
night and the conversation connected a bunch of useful things about
precognition, and I have expanded that here. This post has math, but
simple math, and computer science, but simple computer science, and
magical oracles, but simple magical oracles.
In the story the future and past could be visited and objects and
information exchanged, but the events could not be changed. Another
possibility was brought up, inspired by another story: if you could
see your future and actions then you would see the best possible
future since otherwise you would do something different.
Of course that depends on your actions converging. Consider your
decision as a function F which is applied to the action X you see your
future self performing. The output of F(X) is the action you choose to
perform after seeing action X in your future.
Then there may be a "fixed point" where you see X and still decide to
perform X, because X is obviously the best action to take. I can write
X = F(X)
Now substitute F(X) for X in the right hand side:
X = F(F(X))
X = F(F(F(X)))
X = F(F(F(F(F(F(F(F(....))))))))
So now one can see how to, perhaps, construct X from just F. The
above infinite nesting of F computes what is named the least fixed
point. Most programming implicitly or explicit works like the
infinitely nested F, basically because it allows the program to have
loops and recursion. [ side note: I will not discuss the "Y
combinator" here ].
But consider this F: "if you see yourself turn left then you decide to
turn right, and if you see yourself turn right then you decide to turn
left." This will never converge to a stable answer. Similarly, some
programs never halt - they will loop forever and never have a stable
answer.
In some stories, what you see in the future (or learn from time
travel) affects the future in this recursive way. Sometimes this
looping is explored iteration by iteration (Back to the Future), and
sometimes just the fixed point is experienced (the unchangable past
and future). Stories with multiple parallel worlds/futures will not
concern me here.
Considering finding the fixed point to precognition led me to the
capsule summary of Turing's Halting problem (1936). If some programs
(algorithms) halt and others do not halt then how can you tell the
difference? The traditional nomenclature is that a Turing machine has
a HALTING STATE which it either reaches or does not reach. Some
programs obvious halt, some obviously don't: can one write an program
(algorithm) that reads programs and decides if they halt?
Let us suppose such a program CHECK_HALT existed. This would be a
little like precognition. CHECK_HALT will read an input program & the
data it would be run on and tell you whether running that input
program on that data will eventually halt or will run forever.
CHECK_HALT "predicts the future" halting of the input program run on
the data. Note that it cannot actually run the program on the data
because the program & data may never halt but CHECK_HALT is supposed
to always halt. Thus CHECK_HALT has to be much more clever than just
simulating the future running of the program.
Now I could write a program P with this supposed CHECK_HALT as a
subroutine. This P will read a program Q as input and then run
CHECK_HALT on input program Q & data Q. Then CHECK_HALT will cleverly
simulate running Q on Q. If CHECK_HALT says the input program & data
never halts then P will decide to halt, if CHECK_HALT says the input
program & data halts then P will go into a loop and never halt. This
is analogous to the left versus right turning paradox given
above. Program P will do the *opposite* of what the input program Q
would do.
What happens if P is run and fed the program code for P itself as
input? Thus Q is P and P does the *opposite* of what P would do. Now
look closer. P passed the code for P & data P to the CHECK_HALT
subroutine. If the CHECK_HALT subroutine says P on P would halt then
P decides not to halt. If the CHECK_HALT subroutine says P on P will
not halt then P halts. Either would lead to a contradiction, lead to
a paradox. All this trouble comes from using CHECK_HALT to simulate
itself as part of program P: I see myself predicting left, right,
left, right...
So to avoid paradox, the assumption that CHECK_HALT is a program that
always tells the truth and then halts must be false. Thus:
* CHECK_HALT may not be a program; it may be some infinitely wise and
transcendent "oracle", and I really do mean infinite
* CHECK_HALT may be wrong (tell a lie, make a guess, etc.) about
whether the input program & data halts
* CHECK_HALT may decide that the only possible thing it do when run
on program P & data P is to refuse to give an answer by never halting.
And thus running P with input P will never halt, but this time because
CHECK_HALT goes into an infinite loop. So CHECK_HALT has some inputs
that cause it to loop.
Thus every single clever analysis program CHECK_HALT has at least one
input that it refuses to classify. You cannot beat the logic. In
analogy to precognition and time travel: Maybe this means that people
who insist on being contrary - like in the left and right turn example
- would encounter such a non-answer and fail to see the future to
being with. Maybe people who would go back and kill their grandfather
would never be able to time travel (or would travel but never arrive).
Thus the future in such a story is only "clear" when it will go
unchanged - either no changes will be attempted or all attempts to
change it are doomed to fail. So cryptic oracles that lead the
listener to ironically fulfilling the prophesy fit in just fine. One
could still make a fortune betting on sports or buying lottery
tickets.
Also: if you had CHECK_HALT you could check any mathematical statement
EQ to see if can be proved. Write a program LOOK to start with the
axioms and brute force search all derivations from them until EQ is
found. If CHECK_HALT on LOOK says that LOOK halts then EQ must be
provable. If CHECK_HALT on LOOK says that LOOK never halts then EQ
cannot be proved. This is more than a bit like information for free.
But time travel stories also can feature information for free. The
story last night had the older self tell the younger self where to dig
up buried treasure. How did the older self know? He was told when
younger. [ And even geekier: In Star Trek, who invented transparent
aluminium ? ]
Calling CHECK_HALT and "oracle" is not new thing, the father of
CHECK_HALT named it thus: "[Turing] imagined a God-like computer, much
more powerful than any real computer, which could know the unknowable:
whether a real computer would halt when running a particular program,
or carry on forever. He called this fantastical machine an "oracle". [
http://www-2.dc.uba.ar/profesores/becher/ns.html ]
What is even worse is that mathematician Gregory Chaitin has defined
the Ω number, which is essentially "the probability that a randomly
chosen program halts". Thus Ω is a well defined real number between 0
and 1, and we can compute the first few decimal places. But it is
provably impossible to be completely computed; any attempt will reach
a decimal place where one gets stuck. The answer for the further
digits cannot be obtained from our axioms of mathematics. But
Turing's "oracle" machine knows Ω...
So there are things in mathematics that mathematicians can never see,
many things. If we want to know more digits of Ω there is a simple
program O that never halts: as it runs it starts at 0 and the output
rises getting close and closer to Ω, but never reaching it. Without a
magic "oracle" we can learn more about Ω, but we can only learn it by
running such a program like O and waiting for the
future. "Precognition" of the rest of the digits is logically and
provably impossible, one must grow old instead, and even then the new
digits are not known for certain...
night and the conversation connected a bunch of useful things about
precognition, and I have expanded that here. This post has math, but
simple math, and computer science, but simple computer science, and
magical oracles, but simple magical oracles.
In the story the future and past could be visited and objects and
information exchanged, but the events could not be changed. Another
possibility was brought up, inspired by another story: if you could
see your future and actions then you would see the best possible
future since otherwise you would do something different.
Of course that depends on your actions converging. Consider your
decision as a function F which is applied to the action X you see your
future self performing. The output of F(X) is the action you choose to
perform after seeing action X in your future.
Then there may be a "fixed point" where you see X and still decide to
perform X, because X is obviously the best action to take. I can write
X = F(X)
Now substitute F(X) for X in the right hand side:
X = F(F(X))
X = F(F(F(X)))
X = F(F(F(F(F(F(F(F(....))))))))
So now one can see how to, perhaps, construct X from just F. The
above infinite nesting of F computes what is named the least fixed
point. Most programming implicitly or explicit works like the
infinitely nested F, basically because it allows the program to have
loops and recursion. [ side note: I will not discuss the "Y
combinator" here ].
But consider this F: "if you see yourself turn left then you decide to
turn right, and if you see yourself turn right then you decide to turn
left." This will never converge to a stable answer. Similarly, some
programs never halt - they will loop forever and never have a stable
answer.
In some stories, what you see in the future (or learn from time
travel) affects the future in this recursive way. Sometimes this
looping is explored iteration by iteration (Back to the Future), and
sometimes just the fixed point is experienced (the unchangable past
and future). Stories with multiple parallel worlds/futures will not
concern me here.
Considering finding the fixed point to precognition led me to the
capsule summary of Turing's Halting problem (1936). If some programs
(algorithms) halt and others do not halt then how can you tell the
difference? The traditional nomenclature is that a Turing machine has
a HALTING STATE which it either reaches or does not reach. Some
programs obvious halt, some obviously don't: can one write an program
(algorithm) that reads programs and decides if they halt?
Let us suppose such a program CHECK_HALT existed. This would be a
little like precognition. CHECK_HALT will read an input program & the
data it would be run on and tell you whether running that input
program on that data will eventually halt or will run forever.
CHECK_HALT "predicts the future" halting of the input program run on
the data. Note that it cannot actually run the program on the data
because the program & data may never halt but CHECK_HALT is supposed
to always halt. Thus CHECK_HALT has to be much more clever than just
simulating the future running of the program.
Now I could write a program P with this supposed CHECK_HALT as a
subroutine. This P will read a program Q as input and then run
CHECK_HALT on input program Q & data Q. Then CHECK_HALT will cleverly
simulate running Q on Q. If CHECK_HALT says the input program & data
never halts then P will decide to halt, if CHECK_HALT says the input
program & data halts then P will go into a loop and never halt. This
is analogous to the left versus right turning paradox given
above. Program P will do the *opposite* of what the input program Q
would do.
What happens if P is run and fed the program code for P itself as
input? Thus Q is P and P does the *opposite* of what P would do. Now
look closer. P passed the code for P & data P to the CHECK_HALT
subroutine. If the CHECK_HALT subroutine says P on P would halt then
P decides not to halt. If the CHECK_HALT subroutine says P on P will
not halt then P halts. Either would lead to a contradiction, lead to
a paradox. All this trouble comes from using CHECK_HALT to simulate
itself as part of program P: I see myself predicting left, right,
left, right...
So to avoid paradox, the assumption that CHECK_HALT is a program that
always tells the truth and then halts must be false. Thus:
* CHECK_HALT may not be a program; it may be some infinitely wise and
transcendent "oracle", and I really do mean infinite
* CHECK_HALT may be wrong (tell a lie, make a guess, etc.) about
whether the input program & data halts
* CHECK_HALT may decide that the only possible thing it do when run
on program P & data P is to refuse to give an answer by never halting.
And thus running P with input P will never halt, but this time because
CHECK_HALT goes into an infinite loop. So CHECK_HALT has some inputs
that cause it to loop.
Thus every single clever analysis program CHECK_HALT has at least one
input that it refuses to classify. You cannot beat the logic. In
analogy to precognition and time travel: Maybe this means that people
who insist on being contrary - like in the left and right turn example
- would encounter such a non-answer and fail to see the future to
being with. Maybe people who would go back and kill their grandfather
would never be able to time travel (or would travel but never arrive).
Thus the future in such a story is only "clear" when it will go
unchanged - either no changes will be attempted or all attempts to
change it are doomed to fail. So cryptic oracles that lead the
listener to ironically fulfilling the prophesy fit in just fine. One
could still make a fortune betting on sports or buying lottery
tickets.
Also: if you had CHECK_HALT you could check any mathematical statement
EQ to see if can be proved. Write a program LOOK to start with the
axioms and brute force search all derivations from them until EQ is
found. If CHECK_HALT on LOOK says that LOOK halts then EQ must be
provable. If CHECK_HALT on LOOK says that LOOK never halts then EQ
cannot be proved. This is more than a bit like information for free.
But time travel stories also can feature information for free. The
story last night had the older self tell the younger self where to dig
up buried treasure. How did the older self know? He was told when
younger. [ And even geekier: In Star Trek, who invented transparent
aluminium ? ]
Calling CHECK_HALT and "oracle" is not new thing, the father of
CHECK_HALT named it thus: "[Turing] imagined a God-like computer, much
more powerful than any real computer, which could know the unknowable:
whether a real computer would halt when running a particular program,
or carry on forever. He called this fantastical machine an "oracle". [
http://www-2.dc.uba.ar/profesores/becher/ns.html ]
What is even worse is that mathematician Gregory Chaitin has defined
the Ω number, which is essentially "the probability that a randomly
chosen program halts". Thus Ω is a well defined real number between 0
and 1, and we can compute the first few decimal places. But it is
provably impossible to be completely computed; any attempt will reach
a decimal place where one gets stuck. The answer for the further
digits cannot be obtained from our axioms of mathematics. But
Turing's "oracle" machine knows Ω...
So there are things in mathematics that mathematicians can never see,
many things. If we want to know more digits of Ω there is a simple
program O that never halts: as it runs it starts at 0 and the output
rises getting close and closer to Ω, but never reaching it. Without a
magic "oracle" we can learn more about Ω, but we can only learn it by
running such a program like O and waiting for the
future. "Precognition" of the rest of the digits is logically and
provably impossible, one must grow old instead, and even then the new
digits are not known for certain...