- A non-halting decider is defined - 4 Updates
- C++20 Designated initializers + struct member initializer - 1 Update
| Tim Rentsch <tr.17687@z991.linuxsc.com>: Nov 10 07:40PM -0800 "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes: [...] > So not only was Penrose wrong (which is obvious from his silly result) > but there is necessarily something fishy in Turing's proof (not so > obvious!), because it can't deal with a human as decider. The question is meaningless because what may happen when someone or something "evolves" is not defined. If one assumes that a mechanism, whether human or non-human, may "evolve" so as to solve the halting problem, then the mechanism may solve the halting problem. For the question to have a meaning though, there must be some kind of statement about what kind of changes are possible when the considering agent "evolves". As far as human agents go, all the evidence available so far is that human beings are no better at solving the halting problem than programs (ie, Turing Machines) are, and if anything they are worse. In any case the idea that a person could accept an arbitrary Turing Machine as input and say within some finite time (a thousand years, say) whether it will halt is obviously wrong. Just for starters, the input Turing Machine could be so big it would take more than a thousand years just to read it. > Namely, Turing did not account for evolving deciders -- I believe a > very simple example could be one that is influenced by random numbers. Random numbers don't change anything. Any state change based on a random number can be simulated by a non-deterministic Turing Machine, and deterministic Turing Machines can compute anything a NDTM can. No power is gained by introducing randomness. |
| Tim Woodall <news001@woodall.me.uk>: Nov 11 08:04AM > that human beings are no better at solving the halting problem > than programs (ie, Turing Machines) are, and if anything they are > worse. Agreed! The shift function for a 5 state 2 symbol TM isn't known. There are (at most) $2*6*2^{2*5}$ TMs to investigate. While this is a large number, it's well within the limits of exhaustive search for other similarly sized problems. The remaining (unknown if they halt) machines are known to run for a minimum of (approx) 10^12 steps if they halt at all. The maximum value for a TM that definitely does halt is <50000000. AIUI there are only about 100 machines that are "unknown if they halt". If humans were any good at telling if a machine would halt or not then these remaining ones would have been solved "by inspection" but they haven't been. Tim. |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 11 12:57PM +0100 On 11.11.2020 04:40, Tim Rentsch wrote: > (a thousand years, say) whether it will halt is obviously wrong. > Just for starters, the input Turing Machine could be so big it > would take more than a thousand years just to read it I'm sorry but envisioning humans doing a thing like that without employing computers, is just daft. Like, stupid. > a random number can be simulated by a non-deterministic Turing > Machine, and deterministic Turing Machines can compute anything > a NDTM can. No power is gained by introducing randomness. You can't predict a future random event, so you can't predict the random-influenced machine, so you can't construct an unsolvable case for it. So, your assertion that randomness is irrelevant, is, uhm, just an assertion. I'm not saying your conclusion is necessarily wrong but there's no connection from premise to conclusion; that leap of yours is beyond logic (unless you're postulating a time machine?). - Alf |
| olcott <NoOne@NoWhere.com>: Nov 11 11:06AM -0600 On 10/28/2020 6:43 PM, olcott wrote: > final state of NON_TERMINATING_BEHAVIOR_DETECTED. > If the subordinate UTM terminates normally the halt decider UTM > transitions to its own final state of SUBORDINATE_HAS_TERMINATED. // Simplified version of Linz H_Hat DOES NOT copy itself 01 void H_Hat(u32 P) // (bottom of page 319) 02 { 03 if (H(P, P)) 04 HERE: goto HERE; 05 else 06 HALT 07 } // Linz H with some of the ⊢* states shown 08 bool H(u32 P, u32 I) // Page 318 09 { 10 bool Halted = false; 11 bool Aborted = false; 12 while (!Halted && !Aborted) 13 { 14 Halted = DebugStep(P, I); 15 Aborted = Needs_To_Be_Aborted(); 16 } 17 return !Aborted; 18 } http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. When-so-ever a halt decider correctly determines that its input would never halt unless forced to halt by this halt decider this halt decider has made a correct not-halting determination. Unless H forces its input to halt: H(H_Hat, H_Hat) its first parameter specifies infinite recursion at its line 03. NEW MATERIAL ADDED HERE int main() H_Hat(H_Hat); H_Hat(H_Hat) calls H(H_Hat, H_Hat) that decides that its first parameter (also the parameter to H_Hat) would never halt unless the halt decider forces it to halt. The execution trace proves that this is true. H_Hat was intentionally designed to do the opposite of whatever the halt decider decides to thwart a correct halting decision. The halt decider got smarter and its halting decision is no longer thwarted. The decision of every decider can only be correctly measured against its input. The question is did the decider meet its own criterion measure for its input? When the criterion measure of a halt decider is: Does the input have to be forced to stop to prevent its infinite execution? And the input does have to be forced to stop to prevent its infinite execution. Then the halt decider necessarily made a correct not-halting decision. int main() { H_Hat(H_Hat); H(H_Hat, H_Hat); } In both of the above two cases the input must be forced to halt by the halt decider or it would never halt. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| Brian Wood <woodbrian77@gmail.com>: Nov 11 05:21AM -0800 On Tuesday, November 10, 2020 at 3:41:33 PM UTC-6, Jorgen Grahn wrote: > > language with just two instructions is Turing complete, and thus you > > can implement anything with it. Nothing more is needed. > I see you're not interested in a serious discussion. I don't understand why you say that. I've often found your posts to be thoughtful and interesting. Brian Ebenezer Enterprises https://webEbenezer.net |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment