Hyper Boolean Turing Machine Draft

As we know, the TuringMachine cannot solve its own HaltingProblem. Let us restrict the TuringMachine as follows: The tape consists only of 1, 0, B. The head cannot write B to the tape nor scan past a B (to preserve a B it must turn around). The only result from running the Turing machine we care about is whether the halting state was an accepting state or not (hence the Boolean). It is considered a 4th year proof in CS that this form is still a UniversalTuringMachine as it can accept or not a ContextSensitiveGrammar?.

The best known method for attempting to solve the HaltingProblem for a specific TuringMachine in general form is to run it to conclusion and give-up if it goes into a loop. Obviously there are forms of no-halt that defeat this (running out to the end of infinity, etc.).

But the mathematics involved here for saying this doesn't halt has a flaw. Zeno's paradox is still with us. What if we could observe the end of infinity? For the naive solution math has taken to Zeno's paradox is that time is uniform, but modern physics as taught us that it is not. There exist designer spacetimes in GeneralRelativity that permit inverse time dilation, that we the observer can observe the machine running faster than the observer's own clock. I saw a paper where the author presented such a distorted spacetime where infinite inverse time dilation was attained without infinite blueshift; permitting the signalling of information from inside the space to outside it. I looked at the constraints on his solution and found that it was limited, only the smallest piece can be sent, that I call the HalfBit.

From this point we will assume we may set the laws of physics how we may to build the machine. It's easier this way. (Besides, we're talking about logic, not physics.) We will set as follows: TheSecondLawOfThermodynamics? is suspended. NegativeEnergy? exists. White holes can be constructed and provide the right kind of inverse time dilation. And this is crucial; white holes can be nested.

If we assume the hardware does not fail (and we do), you may pull a trick that a first year ElectricalEngineering? student sometimes discovers, that 3 distinct values may be sent on a single digital wire, and consequently the HalfBit may be promoted to a full bit.

Therefore, to solve the HaltingProblem for a BooleanTuringMachine, one must merely change all states to accept, and run it within the white hole. The HalfBit result will signal 1 if the machine halts and will not signal otherwise. This is the first HyperComputer. There is no debate that it solves the TuringMachine's HaltingProblem.

But solving the TuringMachine's halting problem with a HyperComputer does not directly approach Godel. For a HyperComputer may solve the TuringMachine and a further HyperComputer to solve that one does not threaten either the HaltingProblem or GodelsIncompletenessTheorem? in the least.

The simplest form of the argument that a HyperComputer is constrained to the same HaltingProblem however reads to me like the flawed proof that a QuineProgram does not exist because it must be larger than its source code. We will soon see why.

To adapt this special purpose machine to general purpose, we shall do as follows. Add to the possible operations "begin-extract-tape" and "end-extract-tape-to-whitehole-and-run". These operations mark off the beginning and end of the initial tape to feed into the wormhole. The HyperComputer is now a general purpose HyperComputer that may compute a Boolean function of arbitrary runtime in constant time (notice that we reduced the HaltingProblem itself by setting all states to accepting states to make this a true Boolean function). So now the HyperComputer can do whatever a TuringMachine can do and then some. This I shall call the second HyperComputer (to not be deceived. The first HyperComputer's identity is well-known in literature although it was not described as a white hole, but as an OracleMachine?; however the second HyperComputer is a local definition).

The small step that makes this complete is to change the "run" from run TuringMachine to run HyperComputer. This I shall call the Third Hypercomputer, and the HyperComputer it runs within the white hole is itself. That a machine may construct an exact copy of itself is well known. One of them is known as measles. The machine now has truly enormous power, and may solve the HaltingProblem for the second HyperComputer.

Begin diversion that simplifies the understanding of the collapse of the HaltingProblem.

I shall introduce a weaker HyperComputer that I call the fourth HyperComputer. It is a restricted form of the third HyperComputer that only solves Boolean functions, but starts by wrapping the whole thing in the white hole, so that it solves Boolean functions in constant time. It is easy to see this is still sufficient to solve the halting problem of the third HyperComputer. Now for the fun part. The halting problem for the fourth HyperComputer may be solved by a primitive computer. C++ code to solve it follows:

  bool DoesProgramHalt(FourthHyperComputerProgram p) { return true; }

It is trivial to show that when running on the forth HyperComputer, the infinite loop halts, and by the definition of HalfBit, the result is 0 (an alternate definition of HalfBit with the meaning of power and ground swapped would result in 1). The famous HaltingProblem breaker doesn't work here.

Unfortunately what I thought was a two way link between Godel and halt was a one way link and this particular method does not provide a direct approach against Godel.

End diversion.

It turns out the third HyperComputer is capable of solving its own halting problem. It has programs that do not halt, but the program that can decide if any program halts with any input can be trivially written.

The third HyperComputer is sufficient to write a TheoremSolver?. The basic algorithm is as follows: start with the predicates. Perform bredth-first search of all possible derivations from predicate until we find what we are trying to prove, collapsing consecutive nots so that not(not(x)) becomes x [necessary so I can prove the algorithm works. should work without], and using inconsistency theorem at top level if possible. This algorithm is PSPACE complexity, but is known to work if the thing to be proved can be proved or disproved within the set of logical derivations from the predicates. Now if we set the TheoremSolver? up to check syntax then the halting of the unchecked version on both the problem and its inverse then run the run that halts, we have a complete solver.

There are five possible outputs on input Z.

   Discover Z is not syntactically valid.

   Prove requested Z. Proof published as result.

   Disprove requested Z. Proof published as result.

   Discover the algorithm doesn't halt for this input. The input is independent of the axioms. Publish static proof not(ThirdHyercomputerHalts?(unchecked TheoremSolver?, input)) and not(ThirdHyercomputerHalts?(unchecked TheoremSolver?, not(Z))).

   Discover both proofs exist, therefore the input was a paradox to begin with. Publish both proofs.

If one of the rules if logic is ThirdHypercomputerHalts?(program, input) (forgive me I don't know formal logic syntax beyond predicate, for each, and for all), then the proposed TheoremSolver? can tackle Godel's Fkk.

Here we are faced with a commundrum. Fkk is something that if you prove Fkk you can also prove not(Fkk). But this algorithm must work.

Either Godel isn't saying much of anything (we already knew there were unsolvable problems: a conclusion not referenced by the predicates at all nor covered by a for all is unsolvable), or the hidden assumption in Godel is that it applies only to first order logic, or something in the definition of the machine is incoherent. There are still unsolvable problems, but now we can tell what they are.

Be forewarned, it is still an open problem whether or not the laws of physics that correspond to this universe allow for such a construct as the third HyperComputer to be built. It was proved last year the GrandfatherParadox is not sufficient to categorically rule out backwards time travel, and the base laws of physics allow for the stunt, and the PredestinationParadox? is not a paradox. This means the presence of a paradox that can be constructed by machine is not a paradox in itself and cannot rule out the machine that invoked it. What happens on attempt to invoke is physics takes over and whatever implementation detail that would force-resolve comes up.

I have clearly reached the end of the writing. The HaltingProblem is defeated. GoedelsIncompletenessTheorem is threatened, and in my judgement should fall because I can consistently classify all forms. Curry's paradox (http://en.wikipedia.org/wiki/Curry%27s_paradox) does not hold because paradoxes can be tested for. "Do not assume paradoxes" is not an unfeasible constraint on the engine. The one guy who would entreat with me somehow thinks that GoedelsIncompletenessTheorem still holds and says something important, but I don't see how.

The halting problem for TuringMachines never had a chance of being defeated by the method proposed above for the very simple fact that the above aren't TuringMachines. GoedelsIncompletenessTheorem is completely safe. You don't see how it still holds because, by your admission, you aren't familiar with what it's about. Ones intuitions about subjects they are unfamiliar with are often uncertain.

Goedel's Fkk is a classifiable problem if not a solvable one. The only choices are true, false, paradox, independent. Any of the first three and Goedel collapses, but take the fourth and Goedel didn't say anything we didn't already know much easier. K(z) is independent if z is unbound and forall K and forall not K are both not true.

When talking about natural numbers, Goedel's Fkk is known to be true. In fact, Goedel showed that Fkk was true in the very paper he presented GoedelsIncompletenessTheorem. There is no "collapse" caused by this. It simply means that first order logic isn't powerful enough to prove everything.

The collapse is caused by the machine proving its own Fkk, which Goedel says can't happen. You do realize that the only thing preventing a first-order theorem solver from recognizing Fkk for a class of machines including itself and immediately printing true is Curry's Paradox, right? Also, I couldn't find any claim anywhere until it was written on this page that Goedel is limited to first order logic.

Of course I don't "realize that the only thing preventing a first-order theorem solver from recognizing Fkk for a class of machines including itself and immediately printing true is Curry's paradox". Fkk is a statement of arithmetic, it's not a class of machines at all. As for restrictions to Goedel, it applies to theories that are capable of modeling RobinsonArithmetic and whose proof system can be encoded using arithmetic. Second order Peano arithmetic would be an example of a theory to which Goedel doesn't apply.

I find it convenient to define all formal logic systems in terms of a non-deterministic theorem solver. This trivially provides the effectiveness property.

My apologies. It turned out this first version used an oversimple method. The third HyperComputer is sufficient to write a TheoremSolver?. The basic algorithm is as follows: start with the predicates. Perform bredth-first search of all possible derivations from predicate until we find either what we are trying to prove or its inverse. This algorithm is PSPACE complexity, but is known to work if the thing to be proved or disproved can be proved or disproved within the set of logical derivations from the predicates. Now if we set the TheoremSolver? up to check the halting of the unchecked version then run it only if it halts, we have a complete solver.

There are three possible outputs.

   Prove requested Z. Proof published as result.

   Disprove requested Z. Proof published as result.

   Discover the algorithm doesn't halt for this input. Publish static proof not(ThirdHyercomputerHalts?(unchecked TheoremSolver?, input)).

Preserved chatter until we decide what to do with it.

There's no doubt that some things more powerful than a TuringMachine can solve the halting problem for TuringMachines. Your trick with the white holes would (if it works, I haven't looked into it yet) be something more powerful than a TuringMachine. However, if for any two machines (A, B) we can build a machine such that if (A) then B and another machine such that not(A), then these HyerBooleanTuringMachines? will have their own halting problem which they cannot solve.

You are following the problem well. Wait for the next section.

You don't need all this stuff about second, third, and fourth HyperBooleanTuringMachines? to come up with a class of machines that would solve the halting problem for itself and is a strict superset of the class of TuringMachines. Just do what you did with the fourth HyperComputer with your first one. You make your class of machines be the class of TuringMachines plus the HyperBooleanTuringMachine? that returns true if the code passed to it doesn't represent a TuringMachine and solve the halting problem as above if it is. To put it another way, this class contains all the TuringMachines, and just one HyperBooleanTuringMachine?, the HyperBooleanTuringMachine? that solves the halting problem for this class. This is essentially what you did with your fourth machine, without the obfuscation.

Of course, one would wonder why we can build that HyperBooleanTuringMachine? and not the not(HyperBooleanTuringMachine?). This also applies to your fourth machine.

Hmmm. The path with the four distinct machines is the actual reasoning path I took to develop the thing. I have no idea what you mean by not(HyperBooleanTuringMachine?).

If x is a HyperBooleanTuringMachine?, then not(x) is a HyperBooleanTuringMachine? that returns 0 wherever x returns 1 and returns 1 wherever x return 0.

The white hole is not an implementation detail. It's what distinguishes this from the Zeno machine, in that the behavior is actually defined. The Zeno Machine has no defined behavior for t > 2, but the white hole turns out to cloak the machine at t = 2 so the undefined behavior is wrapped in a singularity that can no longer be observed.

The wonder still exists. Why would you be able to build that particular machine and not the other machines I mentioned?

Because the end of infinity is only defined from an outside context where it makes sense to ask the question in retrospect. This appears to be as inherent in the laws of physics as the second law of thermodynamics.

Doesn't really answer the question. It's easy to build a machine that take a 0 or 1 as input, and returns a 1 or 0 respectively. What keeps us from taking the output from the HyperBooleanTuringMachine? and feeding into the machine that flips 0s and 1s? You seem to expect us to be able to make use of the output, so why can't a machine that we already know exists also make use of it?

Sure you can. This is the construction that makes the second hypercomputer.

Then it doesn't solve it's own halting problem.

But the third hypercomputer can solve its own halting problem.

Can we use the output of the third hypercomputer and feed that into a machine that flips 0s and 1s?

Now about the TheoremSolver?, your first HyperBooleanTuringMachine? can act as a theorem solver for first order theories. It would work in essentially the same manner you used it to solve the halting problem for TuringMachines. Now for a few points.

I realized that immediately, but I had to go as far as the third to be able to publish proofs or get a machine that solves its own halting problem. Fkk is unaddressable in the first because Panything is not defined.

We already know that Fkk is true in the standard model (aka natural numbers) if we assume that RobinsonArithmetic is consistent. This was shown by Godel in the very same paper he proved the incompleteness theorem in.
There are only two possible statuses for Fkk for first order theories. Either there's a proof of Fkk and a proof of ~Fkk, or there's no proof of Fkk and no proof of ~Fkk. A HyperBooleanTuringMachine? would let us know which of those two was actually the case, but it won't prove Fkk and also prove that there is no proof of ~Fkk (or the other way around).
Currently, we are effectively limited to first order theories and first order fragments of higher order theories. HyperBooleanTuringMachines? almost certainly would allow us to expand into theories that are currently out of reach.

But I'm the guy who thinks Godel screwed up and Fkk is a fundamentally broken predicate along the same lines as "This statement is false."

He didn't, and it's not. Above you say you don't know formal logic syntax. I'd suggest that you fix that before you continue on in this crusade. You almost certainly won't have the tools necessary until you do. (If you take this suggestion seriously, you'll, most likely, end up with the same conclusion that everyone else who has seriously studied logic has come too.

"One of them is known as measles"? You mean a (self-replicating machine like a) virus?

"The first HyperComputer's identity is well-known in literature although it was not described as a white hole, but as an oracle ..." You mean an Oracle Machine? http://en.wikipedia.org/wiki/Oracle_machine