Journal tomhudson's Journal: A Turing machine that can solve for the halting problem ... 25
The halting problem is simple enough to describe: Is there any way to determine whether a program will eventually come up with a solution (and halt) or just keep on and on.
http://artzia.com/History/Biography/Turing/
http://kosmoi.com/Computer/Science/Entscheidungsproblem/
The problem with the turing machine is the infinite tape. Just as I can always create a number 1 larger than any number before it, so a tape with an infinite size can always create a program of size+1 greater than that which we've already investigated.
So here's a thought experiment that allows the infinite tape, and yet solves
for the halting problem in every case
MY magic turing device has the following property - for every calculation it
performs, after completion, it goes back in time to when it started, and
continues from where it left off. (hey, if you can have an infinite tape, I
can have non-linear time loops
For example, if its a really slow machine, doing 1 calculation/sec, at the end of every calculation, it goes back one second in time. When it finishes the calculation, it stops going back in time, so all I have to do is see what its doing at T+2 seconds.
The interesting part is that now EVERY problem you can conceive that can halt is calculated by the machine within 1 subjective second. If the machine even exists at T+2 seconds, the program has halted; if not, then its non-halting. Your machine just seems to "disappear", since it's stuck forever shuttling between T and T+1.
Hope you all have a nice weekend, and that this gives some food for thought. --
Update 1
Part of the problem is that people have confused proofs with the actual problem itself.
The problem is to define a series of steps that will always determine whether a problem halts at some point or not. The Chrono Turing Machine (CTM) succeeds.
The "counter-proofs" involve trying, and failing, to prove the contrary, because they cause contradictions. So what? My counter-example, which solves for the alting problem, shows te "proofs" to be less than complete.
For example: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/ch4.html
So here is how we'll show that the halting problem cannot be solved. We'll derive a contradiction by assuming that it can be solved, i.e., that there's a LISP subroutine (halts? s-exp) that returns true or false depending on whether the S-expression s-exp has a value.
Then using this hypothetical solution to the halting problem, we construct a self-referential S-expression the same way that we did in Chapter III. We'll define ``turing'' to be the lambda expression for a function of x that makes x into (('x)('x)) and then halts iff (('x)('x)) doesn't. I.e., the function ``turing'' of x halts iff the function x applied to x doesn't halt. But then applying this function to itself yields a contradiction! Because applying it to itself halts iff applying it to itself doesn't halt!
This technique is all very well and good, except it is NOT the original problem
For example, it could prove or disprove the Riemann Hypothesis by either halting at T+1 if it finds a counter-example, or disappearing at T+1 if there is no counter-example. Remember, it has an infinity of time and tape with which to work in that 1 second, so if there IS a counter-example, it always finds it and halts.
Same with any problem that generates a series of number. Either, at some point, it generates every possible result and halts at T+1, or it doesn't, and disappears at T+1.
A simple check (Score:3, Funny)
If it says it will run forever then you need to check your code. If it says it will halt then you have written good code. If, after feeding it the code, the engine halts you patent it.
I'd wait for quantum computers to become available. Feed it your code and it will execute every possible option and give you the answer.
Re:A simple check (Score:2)
You know, if you close one eye, squint the other, and look sideways a bit, the Chrono Turing Machine and the quantum computer are equivalent.
The quantum computer encodes for all possible states, then collapses into the answer.
If the problem does halt, the CTM goes through all possible states, then gives the answer; or it disappears (it's sort of like a Cheshire Shrodingers' cat).
In other words, if the CTM is, in theory, able to solve the halting problem one way or another in all cases, then a quantu
No typos (Score:2)
"Dammit! I lost another computer to a typo today!"
Re:No typos (Score:2)
Think of ALL the consequences.
You know how people have been wondering about the Fermi Paradox - how we seem to be all alone, even though there should, in theory, be lots of other civilizations out there?
Think what happens if you give this Chrono-Turing Device a non-halting problem ... it keeps going back 1 second in the past, expanding its dataset, etc. Drawing more and more power from the environment, getting more and more massive, until, a second after you started it, everything gets sucked into a bl
Re:No typos (Score:2)
(Except, of course, that "Marooned in Realtime" would be a pretty dull book if Earth no longer existed after the Singularity.)
OT (Score:2)
The perils of moderating while tired....
Re:OT (Score:2)
That's okay, there's other opportunities.
Don't feel so bad - look what happened to this First Post:http://politics.slashdot.org/article.pl?sid= 0 6/04/25/1220231 [slashdot.org] - a total troll, and it still got a +4 Insightful.
Further down, I get into
Your math? (Score:2)
T=0
calc 1, T=T+1, (T=1)
compare current to T=0
calc 2, T=T+1, (T=2)
etc...,
Where does T=-1 enter into it?
Re:Your math? (Score:2)
There's no T=-1.
Start: At T, do a calculation
At T+1: Are we finished?
- Yes: Halt
- No: Return to T
The only way the machine makes it to T+2 is if it has completed the calculation. In other words, the program halts.
So, we have a 2-second (to an independent observer) solution.
Re:Your math? (Score:2)
Re:Your math? (Score:2)
That's okay, we've all been there.
It doesn't work... (Score:1)
Now, feed my machine into itself. If my machine operating on itself halts, it will loop forever - if it doesn't halt, then it halts. There's you basic paradox that invalidates the existence of your ultimate Turing machine halt-tester.
Sorry to burst your bubbl
Re:It doesn't work... (Score:2)
Feed your problem into the Chrono-Turing Machine, not your mod of it.
It will do one of two things - either reach T+2, or not. That your mod of it won't doesn't invalidate it.
That would be like saying that since you modified a program, and it broke, the original program was broken.
Re:It doesn't work... (Score:1)
Build a machine that calls your machine and does the opposite. Create a machine that simply feeds the previous machine into itself. Feed this new machine in your Chrono-Turing machine. Ain't gonna work.
The original problem doesn't use while loops. Find a copy of Tring's paper and read it - it is a very interest
Re:It doesn't work... (Score:2)
So why would I bother building a machine that calls my machine? Once you've shown even 1 instance where it is possible to, in every case, determine whether a program halts or not, the fact that some other construct fa
Re:It doesn't work... (Score:1)
For any mathematical system, there will always be classes of problems that
Re:It doesn't work... (Score:2)
The algorithm (the series of steps involved) is quite simple, and it solves for all cases:
This is a general solution, a description of the steps necessary (algorithm) that solves for all cases.
Re:It doesn't work... (Score:1)
Re:It doesn't work... (Score:2)
The paradox only arises in your encapsulation/modification of the functioning of the machine. By the time it gets to YOUR endless loop, it has already completed its work. The only thing that is disallowed is your application, since it is where the paradox arises.
That you can modify the situation to create a paradox is irrelevant to whether the machine as posited works or not, especially since it solves the problem without creating a paradox.
The original "proof" of the halting problem posits someth
Re:It doesn't work... (Score:1)
When you understand the halting problem better we can continue this discussion.
Re:It doesn't work... (Score:2)
I'm not disallowing machines that you think break my machine. I'm just pointing out that they are broken, not mine.
Your position is the argumentive equivalent to saying typewriters can't exist because its possible to generate a paradoxical statement: "THIS SENTENCE IS FALSE"
Infinite loops are integral to the problem - I use one to make the machine disappear if the problem never halts. That nobody else thought of it that way in the last 70 years isn't my fault, or my problem.
That they were so unimagin
Re:It doesn't work... (Score:1)
Find a good text on computability, complexity and completeness. We can continue to discuss why you are wrong when you actually understand the theory.
Re:It doesn't work... (Score:2)
Where's the paradox? There is none.
Come on - don't tell me that in the last 70 years nobody actually noticed this.
And this result applies no matter what program you feed your version. Whether the original program would have h
Re:It doesn't work... (Score:1)
Maybe I haven't explained my argument properly: Your machine can be quite easily broken by engineering a paradox - just as every other proof of this does.
You have not come up with a magic solution to this p
Re:It doesn't work... (Score:2)
if you look at the code in the original proble, it used a "while(1) {}" construct.
An optimizing compiler would realize this is an expression with no side-effects, and replace it with a semicolon; you'd need to have at least one variable declared volatile, as well as a function to be invoked on an interrupt, to prevent the busy-loop from disappearing.
Saw this back in the early '90s. A guy from Matrox was explaining why they switched from BC3.1 to VCwhatever, because their loops j