Workaround for halting problem
in [Theory]
|
Prev: Computer Theory Researchers: Collaborate with over 14,000 Researchers at MyNetResearch.com
Next: Turing Machine Problem
From: Tim Little on 25 Jun 2010 03:56 On 2010-06-25, Heelium <qtvali(a)gmail.com> wrote: > Anyway, that Turings undecideability proof is disproved by me. Why > you think there is no general case algorithm? Because Turing's proof is valid, and yours is not. - Tim
From: Joshua Cranmer on 25 Jun 2010 18:03 On 06/25/2010 02:37 AM, Heelium wrote: > In real world we have real computers with limited memory - we actually > target only those. And for them we have algorithms, which have some > upper limit. Most modern "interesting" programs do not rely on just the computer's memory for their current state. Multithreaded programs also have thread scheduling as the major source of nondeterminism; I/O (both local and network), can be another source. Some programs will also use a hardware random number generator. By the time you aggregate all of these sources of nonrandomness, your "real world" algorithm would have to mind-boggling amounts of memory even to handle tiny programs. > Anyway, that Turings undecideability proof is disproved by me. Why you > think there is no general case algorithm? Your approach relies on you knowing the upper bound for memory, which is undecidable in the general case. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: Heelium on 27 Jun 2010 19:52 I did show now that my disproof does not apply - it's formal, but it does not prove reality behind that formalness of Turings proof false ;) We can not disprove his proof. On Jun 26, 1:03 am, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/25/2010 02:37 AM, Heelium wrote: > > > In real world we have real computers with limited memory - we actually > > target only those. And for them we have algorithms, which have some > > upper limit. > > Most modern "interesting" programs do not rely on just the computer's > memory for their current state. Multithreaded programs also have thread > scheduling as the major source of nondeterminism; I/O (both local and > network), can be another source. Some programs will also use a hardware > random number generator. By the time you aggregate all of these sources > of nonrandomness, your "real world" algorithm would have to > mind-boggling amounts of memory even to handle tiny programs. > > > Anyway, that Turings undecideability proof is disproved by me. Why you > > think there is no general case algorithm? > > Your approach relies on you knowing the upper bound for memory, which is > undecidable in the general case. > > -- > Beware of bugs in the above code; I have only proved it correct, not > tried it. -- Donald E. Knuth
From: Heelium on 27 Jun 2010 19:52 Look at my 1D Cellular Automata solver in this list. On Jun 26, 1:03 am, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > On 06/25/2010 02:37 AM, Heelium wrote: > > > In real world we have real computers with limited memory - we actually > > target only those. And for them we have algorithms, which have some > > upper limit. > > Most modern "interesting" programs do not rely on just the computer's > memory for their current state. Multithreaded programs also have thread > scheduling as the major source of nondeterminism; I/O (both local and > network), can be another source. Some programs will also use a hardware > random number generator. By the time you aggregate all of these sources > of nonrandomness, your "real world" algorithm would have to > mind-boggling amounts of memory even to handle tiny programs. > > > Anyway, that Turings undecideability proof is disproved by me. Why you > > think there is no general case algorithm? > > Your approach relies on you knowing the upper bound for memory, which is > undecidable in the general case. > > -- > Beware of bugs in the above code; I have only proved it correct, not > tried it. -- Donald E. Knuth
From: Heelium on 27 Jun 2010 19:56
On Jun 26, 1:03 am, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote: > Most modern "interesting" programs do not rely on just the computer's > memory for their current state. Multithreaded programs also have thread > scheduling as the major source of nondeterminism; I/O (both local and > network), can be another source. Some programs will also use a hardware > random number generator. By the time you aggregate all of these sources > of nonrandomness, your "real world" algorithm would have to > mind-boggling amounts of memory even to handle tiny programs. Joshua, I did already fix that in what I call 1D Cellular Automata solver - it does check if cycles are going to grow into infinity. Now I am working on program topology to add solution to Halting Problem and class of similar problems. |