Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #25683 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-11-22 19:24 -0600 |
| Last post | 2020-12-02 02:50 +0000 |
| Articles | 20 on this page of 210 — 9 participants |
Back to article view | Back to comp.theory
It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-22 19:24 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-22 20:56 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-23 03:14 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-22 21:33 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-23 04:03 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-22 22:07 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Misrepresentation of MTs position) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 17:09 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-24 03:39 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-23 22:55 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-23 23:22 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-23 23:23 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 17:07 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-23 11:37 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 17:42 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-23 11:53 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 13:39 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](actual facts) olcott <NoOne@NoWhere.com> - 2020-11-23 13:35 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](actual facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 14:58 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](actual facts) olcott <NoOne@NoWhere.com> - 2020-11-23 14:12 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](actual facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 15:54 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 18:47 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-23 13:00 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-25 16:24 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said) olcott <NoOne@NoWhere.com> - 2020-11-25 11:18 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Mike Terry said)(Here is Proof) olcott <NoOne@NoWhere.com> - 2020-11-23 13:21 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 21:02 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 15:29 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 16:45 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 15:47 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 16:57 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 16:06 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 17:35 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 16:38 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 17:45 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 16:51 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 18:02 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 17:31 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 19:55 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 19:08 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 20:38 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 20:28 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 22:28 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Jeff Barnett <jbb@notatt.com> - 2020-11-23 15:47 -0700
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-23 23:51 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 18:37 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 20:04 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 19:20 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-23 20:49 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 02:53 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 22:18 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 15:41 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) olcott <NoOne@NoWhere.com> - 2020-11-24 09:51 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 16:19 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 10:32 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 16:48 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 11:18 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 11:34 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 13:20 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 19:30 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 13:41 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 23:37 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 18:03 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-25 01:40 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 20:10 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-25 03:20 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](first step) olcott <NoOne@NoWhere.com> - 2020-11-24 21:34 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](validation of halting criteria) olcott <NoOne@NoWhere.com> - 2020-11-24 14:44 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](validation of halting criteria) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-25 02:04 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](validation of halting criteria) olcott <NoOne@NoWhere.com> - 2020-11-24 20:21 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](validation of halting criteria) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 23:10 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](key agreement) olcott <NoOne@NoWhere.com> - 2020-11-24 14:29 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) olcott <NoOne@NoWhere.com> - 2020-11-24 10:46 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 17:04 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 17:05 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) olcott <NoOne@NoWhere.com> - 2020-11-24 11:19 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-24 18:08 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) olcott <NoOne@NoWhere.com> - 2020-11-24 12:27 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 13:42 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 13:31 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2020-11-24 12:31 -0800
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 15:46 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2020-11-24 17:22 -0800
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) olcott <NoOne@NoWhere.com> - 2020-11-24 19:35 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 23:14 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) olcott <NoOne@NoWhere.com> - 2020-11-24 14:48 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-25 16:45 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](infallible) olcott <NoOne@NoWhere.com> - 2020-11-25 11:21 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](infallible) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-25 21:25 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) olcott <NoOne@NoWhere.com> - 2020-11-25 15:55 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-25 23:31 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) olcott <NoOne@NoWhere.com> - 2020-11-25 17:47 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 00:33 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) olcott <NoOne@NoWhere.com> - 2020-11-25 18:51 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 01:38 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) olcott <NoOne@NoWhere.com> - 2020-11-25 20:14 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 04:27 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-25 22:39 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 15:48 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 10:07 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 16:30 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 10:41 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 17:08 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 11:34 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 19:36 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 13:58 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 20:28 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 14:32 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 20:43 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 14:48 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 14:50 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 21:12 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 15:16 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 21:27 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 15:48 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-27 01:44 +0000
Re: It is known that a correct halt decider must return false (in olcott <NoOne@nospicedham.NoWhere.com> - 2020-11-26 20:55 -0600
Re: It is known that a correct halt decider must return false (in Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-27 20:12 +0000
Re: It is known that a correct halt decider must return false (in olcott <NoOne@NoWhere.com> - 2020-11-27 14:24 -0600
Re: It is known that a correct halt decider must return false (logical foundation) olcott <NoOne@NoWhere.com> - 2020-11-27 14:29 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Richard Damon <Richard@Damon-Family.org> - 2020-11-26 16:14 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 15:31 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-26 21:57 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 16:05 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-27 01:10 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 21:04 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Richard Damon <Richard@Damon-Family.org> - 2020-11-26 22:48 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) olcott <NoOne@NoWhere.com> - 2020-11-27 09:23 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 11:28 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) olcott <NoOne@NoWhere.com> - 2020-11-27 10:43 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 12:50 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) olcott <NoOne@NoWhere.com> - 2020-11-27 12:32 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) olcott <NoOne@NoWhere.com> - 2020-11-27 12:36 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 13:48 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) olcott <NoOne@NoWhere.com> - 2020-11-27 13:23 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 16:34 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-27 20:28 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) olcott <NoOne@NoWhere.com> - 2020-11-27 14:36 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) olcott <NoOne@NoWhere.com> - 2020-11-27 14:40 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-27 21:03 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels) olcott <NoOne@NoWhere.com> - 2020-11-27 15:12 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) Richard Damon <Richard@Damon-Family.org> - 2020-11-26 17:49 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) olcott <NoOne@NoWhere.com> - 2020-11-26 17:01 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) olcott <NoOne@NoWhere.com> - 2020-11-29 16:33 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-30 00:38 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) olcott <NoOne@NoWhere.com> - 2020-11-29 19:16 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-30 02:38 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) olcott <NoOne@NoWhere.com> - 2020-11-29 21:12 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-30 03:23 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) olcott <NoOne@NoWhere.com> - 2020-11-29 21:53 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Jeff Barnett <jbb@notatt.com> - 2020-11-29 21:31 -0700
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-30 21:28 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](infinite recursion slaps them in the face and they deny it) olcott <NoOne@NoWhere.com> - 2020-11-30 15:31 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Richard Damon <Richard@Damon-Family.org> - 2020-11-30 10:36 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) olcott <NoOne@NoWhere.com> - 2020-11-30 09:55 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Richard Damon <Richard@Damon-Family.org> - 2020-11-30 12:56 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) olcott <NoOne@NoWhere.com> - 2020-11-30 12:10 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) Richard Damon <Richard@Damon-Family.org> - 2020-11-30 15:34 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-24 03:53 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-23 23:29 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-24 15:53 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-24 10:27 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-25 00:16 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) olcott <NoOne@NoWhere.com> - 2020-11-24 18:30 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 23:17 -0500
Re: It is known that a correct halt decider must return false (This is the whole thing) olcott <NoOne@NoWhere.com> - 2020-11-24 22:43 -0600
Re: It is known that a correct halt decider must return false (This is the whole thing) Richard Damon <Richard@Damon-Family.org> - 2020-11-24 23:53 -0500
Re: It is known that a correct halt decider must return false (This is the whole thing) olcott <NoOne@NoWhere.com> - 2020-11-24 23:12 -0600
Re: It is known that a correct halt decider must return false (This is the whole thing) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 07:39 -0500
Re: It is known that a correct halt decider must return false (This is the whole thing) olcott <NoOne@NoWhere.com> - 2020-11-25 08:17 -0600
Re: It is known that a correct halt decider must return false (This is the whole thing) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 10:14 -0500
Re: It is known that a correct halt decider must return false (This is the whole thing) olcott <NoOne@NoWhere.com> - 2020-11-25 09:52 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Linz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-25 22:16 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) olcott <NoOne@NoWhere.com> - 2020-11-25 16:25 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 18:35 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) olcott <NoOne@NoWhere.com> - 2020-11-25 17:59 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 19:55 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) olcott <NoOne@NoWhere.com> - 2020-11-25 19:03 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 21:55 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) olcott <NoOne@NoWhere.com> - 2020-11-25 21:06 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 22:34 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2020-11-25 15:53 -0800
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) olcott <NoOne@NoWhere.com> - 2020-11-25 18:09 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 20:09 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2020-11-25 20:40 -0800
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) olcott <NoOne@NoWhere.com> - 2020-11-25 22:58 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-26 02:06 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a) olcott <NoOne@NoWhere.com> - 2020-11-25 20:33 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a) Richard Damon <Richard@Damon-Family.org> - 2020-11-25 22:00 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a) olcott <NoOne@NoWhere.com> - 2020-11-25 21:08 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-27 17:31 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a) olcott <NoOne@NoWhere.com> - 2020-11-27 12:28 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-28 03:02 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-27 21:53 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-28 16:02 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-28 10:14 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-28 08:18 -0800
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-28 10:25 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-30 01:42 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-29 20:26 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-01 01:30 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Do You Really Still Not Get This?) olcott <NoOne@NoWhere.com> - 2020-11-30 19:43 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Do You Really Still Not Get This?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-02 02:42 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Do You Really Still Not Get This?) olcott <NoOne@NoWhere.com> - 2020-12-01 20:56 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](Do You Really Still Not Get This?) Richard Damon <Richard@Damon-Family.org> - 2020-12-01 22:40 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](Do You Really Still Not Get This?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-03 02:16 +0000
Re: It is known that a correct halt decider must return false (in this case)[V4](Do You Really Still Not Get This?) olcott <NoOne@NoWhere.com> - 2020-12-02 20:37 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Richard Damon <Richard@Damon-Family.org> - 2020-11-30 21:09 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-30 22:02 -0600
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Richard Damon <Richard@Damon-Family.org> - 2020-12-01 06:51 -0500
Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-02 02:50 +0000
Page 5 of 11 — ← Prev page 1 … 3 4 [5] 6 7 … 11 Next page →
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-11-24 15:46 -0500 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) |
| Message-ID | <xievH.27753$Uz.20561@fx46.iad> |
| In reply to | #25829 |
On 11/24/20 3:31 PM, dklei...@gmail.com wrote:
> On Tuesday, November 24, 2020 at 8:19:46 AM UTC-8, Mike Terry wrote:
>> On 24/11/2020 15:51, olcott wrote:
>>> On 11/24/2020 9:41 AM, Mike Terry wrote:
>>>> On 24/11/2020 04:18, olcott wrote:
>>>>> On 11/23/2020 8:53 PM, Mike Terry wrote:
>>>>>> On 24/11/2020 00:37, olcott wrote:
>>>>>>> On 11/23/2020 5:51 PM, Mike Terry wrote:
>>>>>>>> On 23/11/2020 21:29, olcott wrote:
>>>>>>>>> On 11/23/2020 3:02 PM, Mike Terry wrote:
>>>>>>>>>> On 23/11/2020 01:24, olcott wrote:
>>>>>>>>>>> The following shows exactly how the Peter Linz H would correctly
>>>>>>>>>>> decide
>>>>>>>>>>> halting on the Peter Linz Ĥ. This is fully operational code
>>>>>>>>>>> that has
>>>>>>>>>>> been executed in the x86utm operating system that I wrote.
>>>>>>>>>>>
>>>>>>>>>>> To make the Linz counter-example conform to the standard halting
>>>>>>>>>>> problem
>>>>>>>>>>> counter-examples the input is not copied as it is in Linz.
>>>>>>>>>>>
>>>>>>>>>>> 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.
>>>>>>>>>>>
>>>>>>>>>>> x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
>>>>>>>>>>> The x86 language is computationally equivalent to a UTM for all
>>>>>>>>>>> computations that do not require more memory than is available.
>>>>>>>>>>>
>>>>>>>>>>> Recursion can be directly simulated by a UTM that simulates its
>>>>>>>>>>> own
>>>>>>>>>>> Turing machine Description. Infinite recursion would repeat the
>>>>>>>>>>> same
>>>>>>>>>>> state transitions every time the UTM simulates its own Turing
>>>>>>>>>>> machine
>>>>>>>>>>> Description.
>>>>>>>>>>>
>>>>>>>>>>> // Defined at the bottom of page 319 of Linz
>>>>>>>>>>> void Ĥ(u32 P)
>>>>>>>>>>> {
>>>>>>>>>>> u32 Input_Halts = H(P, P);
>>>>>>>>>>> if (!Input_Halts)
>>>>>>>>>>> HALT
>>>>>>>>>>> else
>>>>>>>>>>> HERE: goto HERE;
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> int main()
>>>>>>>>>>> {
>>>>>>>>>>> u32 P = (u32)Ĥ;
>>>>>>>>>>> H(P, P);
>>>>>>>>>>> HALT;
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Disassembled x86 machine language of the above pair of C
>>>>>>>>>>> functions.
>>>>>>>>>>>
>>>>>>>>>>> Ĥ()
>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>> [00000508](03) 83c408 add esp,+08
>>>>>>>>>>> [0000050b](03) 8945fc mov [ebp-04],eax
>>>>>>>>>>> [0000050e](04) 837dfc00 cmp dword [ebp-04],+00
>>>>>>>>>>> [00000512](02) 7403 jz 00000517
>>>>>>>>>>> [00000514](01) f4 hlt
>>>>>>>>>>> [00000515](02) eb02 jmp 00000519
>>>>>>>>>>> [00000517](02) ebfe jmp 00000517
>>>>>>>>>>> [00000519](02) 8be5 mov esp,ebp
>>>>>>>>>>> [0000051b](01) 5d pop ebp
>>>>>>>>>>> [0000051c](01) c3 ret
>>>>>>>>>>>
>>>>>>>>>>> _main()
>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>> [0000053f](03) 83c408 add esp,+08
>>>>>>>>>>> [00000542](01) f4 hlt
>>>>>>>>>>> [00000543](02) 8be5 mov esp,ebp
>>>>>>>>>>> [00000545](01) 5d pop ebp
>>>>>>>>>>> [00000546](01) c3 ret
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Output_Debug_Trace() [00010abc] size(148) capacity(65536)
>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>> 25 instructions
>>>>>>>>>>>
>>>>>>>>>>> The above is where the halt decider aborts the whole Ĥ(Ĥ)
>>>>>>>>>>> invocation
>>>>>>>>>>> sequence because the halt decider detects infinite recursion.
>>>>>>>>>>>
>>>>>>>>>>> In this case infinite recursion is a function call to the same
>>>>>>>>>>> function
>>>>>>>>>>> from the same machine address without any conditional branch
>>>>>>>>>>> instructions that would terminate this recursion.
>>>>>>>>>>
>>>>>>>>>> Hey, you're totally CHEATING here. There ARE conditional branch
>>>>>>>>>> intstructions, but you've just silently snipped them from the trace
>>>>>>>>>> output you've shown. There are HUGE gaps in your trace!!
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Mike.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Unless we maintain a line-of-demarcation between the halt decider
>>>>>>>>> and
>>>>>>>>> its input pathological self-reference(Olcott 2004) makes the halting
>>>>>>>>> problem have undecidable inputs in the same way that the Liar
>>>>>>>>> Paradox is
>>>>>>>>> neither true nor false.
>>>>>>>>>
>>>>>>>>> https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ
>>>>>>>>>
>>>>>>>>> Instead of asking the question: Does the input halt on its input?
>>>>>>>>> that is subject to pathological self-reference.
>>>>>>>>>
>>>>>>>>> We ask the question: Does the execution of the input have to be
>>>>>>>>> aborted
>>>>>>>>> to prevent its infinite execution?
>>>>>>>>>
>>>>>>>>> When we ask this latter question then we can ignore all of the
>>>>>>>>> conditional branch instructions that are in the halt decider and
>>>>>>>>> only
>>>>>>>>> pay attention to the ones that are in the input.
>>>>>>>>>
>>>>>>>>
>>>>>>>> We can indeed ignore the halt decider outer-level trace entries, and
>>>>>>>> concentrate on just what the halt decider embedded emulator sees its
>>>>>>>> input doing.
>>>>>>>
>>>>>>> All that I have right now is a DebugTrace() of all the user specified
>>>>>>> code. This provides a very obvious basis for a halt decider's correct
>>>>>>> halting decision of the H_Hat code specified in this execution trace.
>>>>>>>
>>>>>>> There will not be an embedded decider because an embedded decider
>>>>>>> permits what would seem to causal observers as inconsistent halting
>>>>>>> decisions. By not allowing any execution trace data to exist that the
>>>>>>> halt decider cannot see then even the apperance of inconsistency
>>>>>>> ceases
>>>>>>> to exist.
>>>>>>
>>>>>> There has to be an embedded decider, because that is how the Linz
>>>>>> proof specifies H^. When you say "seem to causal [sic] observers as
>>>>>> inconsistent halting decisions" that is because the decisions really
>>>>>> are inconsistent! You can't magic them to be consistent by making the
>>>>>> decider part of the OS. (If that's your plan.)
>>>>>
>>>>> I do not have to conform to any conventions but this one:
>>>>>
>>>>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>>>>> H.q0 wMw ⊢* H.no if M applied to w would not halt.
>>>>>
>>>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>>>> expresses behavior that is not halting behavior.
>>>>>
>>>>
>>>> Wrong.
>>>>
>>>> You are talking here about H, whereas I was talking about H^. If you
>>>> want to say anything about the Linz proof, you need to talk about H
>>>> *and* H^, and H^ must follow the Linz spec for how it relates to H. Duh.
>>>
>>> Before we can proceed we need to have agreement on this general
>>> principle: (It is a mandatory prerequisite).
>>>
>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>> expresses behavior that is not halting behavior.
>> That's a bad wording for lots of reasons. If I agree to it as it
>> stands, I know you will take that quote and post it all over the
>> newsgroup claiming it means something it doesn't. Because that's the
>> kind of guy that you are.
>>
>> However, I'll happily agree to the better worded:
>>
>> Any input (TMD, DATA) which, when run under a (pure) UTM
>> never halts, expresses behaviour that is not halting behaviour.
>
> I wonder - doesn't the "input" to a Turing Machine simulation also
> need an initial head position specification? It is trivial to design a
> tape that halts for some initial head positions but not for others.
>
Yes, the specification of the tape would include the initial position.
For some machines, it starts at a physical end of the tape, and the tape
only goes on infinitely in one direction. For machines with bidirection
tapes, there is a '0' cell which is the starting point.
[toc] | [prev] | [next] | [standalone]
| From | "dklei...@gmail.com" <dkleinecke@gmail.com> |
|---|---|
| Date | 2020-11-24 17:22 -0800 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) |
| Message-ID | <0087b712-5771-48fe-ae0c-f1c8854939f7n@googlegroups.com> |
| In reply to | #25833 |
On Tuesday, November 24, 2020 at 12:46:25 PM UTC-8, Richard Damon wrote:
> On 11/24/20 3:31 PM, dklei...@gmail.com wrote:
> > On Tuesday, November 24, 2020 at 8:19:46 AM UTC-8, Mike Terry wrote:
> >> On 24/11/2020 15:51, olcott wrote:
> >>> On 11/24/2020 9:41 AM, Mike Terry wrote:
> >>>> On 24/11/2020 04:18, olcott wrote:
> >>>>> On 11/23/2020 8:53 PM, Mike Terry wrote:
> >>>>>> On 24/11/2020 00:37, olcott wrote:
> >>>>>>> On 11/23/2020 5:51 PM, Mike Terry wrote:
> >>>>>>>> On 23/11/2020 21:29, olcott wrote:
> >>>>>>>>> On 11/23/2020 3:02 PM, Mike Terry wrote:
> >>>>>>>>>> On 23/11/2020 01:24, olcott wrote:
> >>>>>>>>>>> The following shows exactly how the Peter Linz H would correctly
> >>>>>>>>>>> decide
> >>>>>>>>>>> halting on the Peter Linz Ĥ. This is fully operational code
> >>>>>>>>>>> that has
> >>>>>>>>>>> been executed in the x86utm operating system that I wrote.
> >>>>>>>>>>>
> >>>>>>>>>>> To make the Linz counter-example conform to the standard halting
> >>>>>>>>>>> problem
> >>>>>>>>>>> counter-examples the input is not copied as it is in Linz.
> >>>>>>>>>>>
> >>>>>>>>>>> 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.
> >>>>>>>>>>>
> >>>>>>>>>>> x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
> >>>>>>>>>>> The x86 language is computationally equivalent to a UTM for all
> >>>>>>>>>>> computations that do not require more memory than is available.
> >>>>>>>>>>>
> >>>>>>>>>>> Recursion can be directly simulated by a UTM that simulates its
> >>>>>>>>>>> own
> >>>>>>>>>>> Turing machine Description. Infinite recursion would repeat the
> >>>>>>>>>>> same
> >>>>>>>>>>> state transitions every time the UTM simulates its own Turing
> >>>>>>>>>>> machine
> >>>>>>>>>>> Description.
> >>>>>>>>>>>
> >>>>>>>>>>> // Defined at the bottom of page 319 of Linz
> >>>>>>>>>>> void Ĥ(u32 P)
> >>>>>>>>>>> {
> >>>>>>>>>>> u32 Input_Halts = H(P, P);
> >>>>>>>>>>> if (!Input_Halts)
> >>>>>>>>>>> HALT
> >>>>>>>>>>> else
> >>>>>>>>>>> HERE: goto HERE;
> >>>>>>>>>>> }
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>> int main()
> >>>>>>>>>>> {
> >>>>>>>>>>> u32 P = (u32)Ĥ;
> >>>>>>>>>>> H(P, P);
> >>>>>>>>>>> HALT;
> >>>>>>>>>>> }
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>> Disassembled x86 machine language of the above pair of C
> >>>>>>>>>>> functions.
> >>>>>>>>>>>
> >>>>>>>>>>> Ĥ()
> >>>>>>>>>>> [000004f7](01) 55 push ebp
> >>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
> >>>>>>>>>>> [000004fa](01) 51 push ecx
> >>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
> >>>>>>>>>>> [000004fe](01) 50 push eax
> >>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
> >>>>>>>>>>> [00000502](01) 51 push ecx
> >>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
> >>>>>>>>>>> [00000508](03) 83c408 add esp,+08
> >>>>>>>>>>> [0000050b](03) 8945fc mov [ebp-04],eax
> >>>>>>>>>>> [0000050e](04) 837dfc00 cmp dword [ebp-04],+00
> >>>>>>>>>>> [00000512](02) 7403 jz 00000517
> >>>>>>>>>>> [00000514](01) f4 hlt
> >>>>>>>>>>> [00000515](02) eb02 jmp 00000519
> >>>>>>>>>>> [00000517](02) ebfe jmp 00000517
> >>>>>>>>>>> [00000519](02) 8be5 mov esp,ebp
> >>>>>>>>>>> [0000051b](01) 5d pop ebp
> >>>>>>>>>>> [0000051c](01) c3 ret
> >>>>>>>>>>>
> >>>>>>>>>>> _main()
> >>>>>>>>>>> [00000527](01) 55 push ebp
> >>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
> >>>>>>>>>>> [0000052a](01) 51 push ecx
> >>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
> >>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
> >>>>>>>>>>> [00000535](01) 50 push eax
> >>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
> >>>>>>>>>>> [00000539](01) 51 push ecx
> >>>>>>>>>>> [0000053a](05) e838feffff call 00000377
> >>>>>>>>>>> [0000053f](03) 83c408 add esp,+08
> >>>>>>>>>>> [00000542](01) f4 hlt
> >>>>>>>>>>> [00000543](02) 8be5 mov esp,ebp
> >>>>>>>>>>> [00000545](01) 5d pop ebp
> >>>>>>>>>>> [00000546](01) c3 ret
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>>
> >>>>>>>>>>> Output_Debug_Trace() [00010abc] size(148) capacity(65536)
> >>>>>>>>>>> [00000527](01) 55 push ebp
> >>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
> >>>>>>>>>>> [0000052a](01) 51 push ecx
> >>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
> >>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
> >>>>>>>>>>> [00000535](01) 50 push eax
> >>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
> >>>>>>>>>>> [00000539](01) 51 push ecx
> >>>>>>>>>>> [0000053a](05) e838feffff call 00000377
> >>>>>>>>>>> [000004f7](01) 55 push ebp
> >>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
> >>>>>>>>>>> [000004fa](01) 51 push ecx
> >>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
> >>>>>>>>>>> [000004fe](01) 50 push eax
> >>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
> >>>>>>>>>>> [00000502](01) 51 push ecx
> >>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
> >>>>>>>>>>> [000004f7](01) 55 push ebp
> >>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
> >>>>>>>>>>> [000004fa](01) 51 push ecx
> >>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
> >>>>>>>>>>> [000004fe](01) 50 push eax
> >>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
> >>>>>>>>>>> [00000502](01) 51 push ecx
> >>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
> >>>>>>>>>>> 25 instructions
> >>>>>>>>>>>
> >>>>>>>>>>> The above is where the halt decider aborts the whole Ĥ(Ĥ)
> >>>>>>>>>>> invocation
> >>>>>>>>>>> sequence because the halt decider detects infinite recursion.
> >>>>>>>>>>>
> >>>>>>>>>>> In this case infinite recursion is a function call to the same
> >>>>>>>>>>> function
> >>>>>>>>>>> from the same machine address without any conditional branch
> >>>>>>>>>>> instructions that would terminate this recursion.
> >>>>>>>>>>
> >>>>>>>>>> Hey, you're totally CHEATING here. There ARE conditional branch
> >>>>>>>>>> intstructions, but you've just silently snipped them from the trace
> >>>>>>>>>> output you've shown. There are HUGE gaps in your trace!!
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>> Mike.
> >>>>>>>>>>
> >>>>>>>>>
> >>>>>>>>> Unless we maintain a line-of-demarcation between the halt decider
> >>>>>>>>> and
> >>>>>>>>> its input pathological self-reference(Olcott 2004) makes the halting
> >>>>>>>>> problem have undecidable inputs in the same way that the Liar
> >>>>>>>>> Paradox is
> >>>>>>>>> neither true nor false.
> >>>>>>>>>
> >>>>>>>>> https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ
> >>>>>>>>>
> >>>>>>>>> Instead of asking the question: Does the input halt on its input?
> >>>>>>>>> that is subject to pathological self-reference.
> >>>>>>>>>
> >>>>>>>>> We ask the question: Does the execution of the input have to be
> >>>>>>>>> aborted
> >>>>>>>>> to prevent its infinite execution?
> >>>>>>>>>
> >>>>>>>>> When we ask this latter question then we can ignore all of the
> >>>>>>>>> conditional branch instructions that are in the halt decider and
> >>>>>>>>> only
> >>>>>>>>> pay attention to the ones that are in the input.
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>> We can indeed ignore the halt decider outer-level trace entries, and
> >>>>>>>> concentrate on just what the halt decider embedded emulator sees its
> >>>>>>>> input doing.
> >>>>>>>
> >>>>>>> All that I have right now is a DebugTrace() of all the user specified
> >>>>>>> code. This provides a very obvious basis for a halt decider's correct
> >>>>>>> halting decision of the H_Hat code specified in this execution trace.
> >>>>>>>
> >>>>>>> There will not be an embedded decider because an embedded decider
> >>>>>>> permits what would seem to causal observers as inconsistent halting
> >>>>>>> decisions. By not allowing any execution trace data to exist that the
> >>>>>>> halt decider cannot see then even the apperance of inconsistency
> >>>>>>> ceases
> >>>>>>> to exist.
> >>>>>>
> >>>>>> There has to be an embedded decider, because that is how the Linz
> >>>>>> proof specifies H^. When you say "seem to causal [sic] observers as
> >>>>>> inconsistent halting decisions" that is because the decisions really
> >>>>>> are inconsistent! You can't magic them to be consistent by making the
> >>>>>> decider part of the OS. (If that's your plan.)
> >>>>>
> >>>>> I do not have to conform to any conventions but this one:
> >>>>>
> >>>>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
> >>>>> H.q0 wMw ⊢* H.no if M applied to w would not halt.
> >>>>>
> >>>>> Any input TMD that would never halt unless a UTM stopped simulating it
> >>>>> expresses behavior that is not halting behavior.
> >>>>>
> >>>>
> >>>> Wrong.
> >>>>
> >>>> You are talking here about H, whereas I was talking about H^. If you
> >>>> want to say anything about the Linz proof, you need to talk about H
> >>>> *and* H^, and H^ must follow the Linz spec for how it relates to H. Duh.
> >>>
> >>> Before we can proceed we need to have agreement on this general
> >>> principle: (It is a mandatory prerequisite).
> >>>
> >>> Any input TMD that would never halt unless a UTM stopped simulating it
> >>> expresses behavior that is not halting behavior.
> >> That's a bad wording for lots of reasons. If I agree to it as it
> >> stands, I know you will take that quote and post it all over the
> >> newsgroup claiming it means something it doesn't. Because that's the
> >> kind of guy that you are.
> >>
> >> However, I'll happily agree to the better worded:
> >>
> >> Any input (TMD, DATA) which, when run under a (pure) UTM
> >> never halts, expresses behaviour that is not halting behaviour.
> >
> > I wonder - doesn't the "input" to a Turing Machine simulation also
> > need an initial head position specification? It is trivial to design a
> > tape that halts for some initial head positions but not for others.
> >
> Yes, the specification of the tape would include the initial position.
> For some machines, it starts at a physical end of the tape, and the tape
> only goes on infinitely in one direction. For machines with bidirection
> tapes, there is a '0' cell which is the starting point.
I like to think of the tape as a pair of stacks plus a head. This does
provide a clear initial position. But without a specific position how
can one know which cell the initial cell under the head is? Are we
assuming that the tape is an array indexed by all integers?
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-24 19:35 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) |
| Message-ID | <0YCdnZPP141KKSDCnZ2dnUU7-R2dnZ2d@giganews.com> |
| In reply to | #25877 |
On 11/24/2020 7:22 PM, dklei...@gmail.com wrote:
> On Tuesday, November 24, 2020 at 12:46:25 PM UTC-8, Richard Damon wrote:
>> On 11/24/20 3:31 PM, dklei...@gmail.com wrote:
>>> On Tuesday, November 24, 2020 at 8:19:46 AM UTC-8, Mike Terry wrote:
>>>> On 24/11/2020 15:51, olcott wrote:
>>>>> On 11/24/2020 9:41 AM, Mike Terry wrote:
>>>>>> On 24/11/2020 04:18, olcott wrote:
>>>>>>> On 11/23/2020 8:53 PM, Mike Terry wrote:
>>>>>>>> On 24/11/2020 00:37, olcott wrote:
>>>>>>>>> On 11/23/2020 5:51 PM, Mike Terry wrote:
>>>>>>>>>> On 23/11/2020 21:29, olcott wrote:
>>>>>>>>>>> On 11/23/2020 3:02 PM, Mike Terry wrote:
>>>>>>>>>>>> On 23/11/2020 01:24, olcott wrote:
>>>>>>>>>>>>> The following shows exactly how the Peter Linz H would correctly
>>>>>>>>>>>>> decide
>>>>>>>>>>>>> halting on the Peter Linz Ĥ. This is fully operational code
>>>>>>>>>>>>> that has
>>>>>>>>>>>>> been executed in the x86utm operating system that I wrote.
>>>>>>>>>>>>>
>>>>>>>>>>>>> To make the Linz counter-example conform to the standard halting
>>>>>>>>>>>>> problem
>>>>>>>>>>>>> counter-examples the input is not copied as it is in Linz.
>>>>>>>>>>>>>
>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>
>>>>>>>>>>>>> x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
>>>>>>>>>>>>> The x86 language is computationally equivalent to a UTM for all
>>>>>>>>>>>>> computations that do not require more memory than is available.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Recursion can be directly simulated by a UTM that simulates its
>>>>>>>>>>>>> own
>>>>>>>>>>>>> Turing machine Description. Infinite recursion would repeat the
>>>>>>>>>>>>> same
>>>>>>>>>>>>> state transitions every time the UTM simulates its own Turing
>>>>>>>>>>>>> machine
>>>>>>>>>>>>> Description.
>>>>>>>>>>>>>
>>>>>>>>>>>>> // Defined at the bottom of page 319 of Linz
>>>>>>>>>>>>> void Ĥ(u32 P)
>>>>>>>>>>>>> {
>>>>>>>>>>>>> u32 Input_Halts = H(P, P);
>>>>>>>>>>>>> if (!Input_Halts)
>>>>>>>>>>>>> HALT
>>>>>>>>>>>>> else
>>>>>>>>>>>>> HERE: goto HERE;
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> int main()
>>>>>>>>>>>>> {
>>>>>>>>>>>>> u32 P = (u32)Ĥ;
>>>>>>>>>>>>> H(P, P);
>>>>>>>>>>>>> HALT;
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Disassembled x86 machine language of the above pair of C
>>>>>>>>>>>>> functions.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Ĥ()
>>>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>>>> [00000508](03) 83c408 add esp,+08
>>>>>>>>>>>>> [0000050b](03) 8945fc mov [ebp-04],eax
>>>>>>>>>>>>> [0000050e](04) 837dfc00 cmp dword [ebp-04],+00
>>>>>>>>>>>>> [00000512](02) 7403 jz 00000517
>>>>>>>>>>>>> [00000514](01) f4 hlt
>>>>>>>>>>>>> [00000515](02) eb02 jmp 00000519
>>>>>>>>>>>>> [00000517](02) ebfe jmp 00000517
>>>>>>>>>>>>> [00000519](02) 8be5 mov esp,ebp
>>>>>>>>>>>>> [0000051b](01) 5d pop ebp
>>>>>>>>>>>>> [0000051c](01) c3 ret
>>>>>>>>>>>>>
>>>>>>>>>>>>> _main()
>>>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>>>> [0000053f](03) 83c408 add esp,+08
>>>>>>>>>>>>> [00000542](01) f4 hlt
>>>>>>>>>>>>> [00000543](02) 8be5 mov esp,ebp
>>>>>>>>>>>>> [00000545](01) 5d pop ebp
>>>>>>>>>>>>> [00000546](01) c3 ret
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Output_Debug_Trace() [00010abc] size(148) capacity(65536)
>>>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>>>> 25 instructions
>>>>>>>>>>>>>
>>>>>>>>>>>>> The above is where the halt decider aborts the whole Ĥ(Ĥ)
>>>>>>>>>>>>> invocation
>>>>>>>>>>>>> sequence because the halt decider detects infinite recursion.
>>>>>>>>>>>>>
>>>>>>>>>>>>> In this case infinite recursion is a function call to the same
>>>>>>>>>>>>> function
>>>>>>>>>>>>> from the same machine address without any conditional branch
>>>>>>>>>>>>> instructions that would terminate this recursion.
>>>>>>>>>>>>
>>>>>>>>>>>> Hey, you're totally CHEATING here. There ARE conditional branch
>>>>>>>>>>>> intstructions, but you've just silently snipped them from the trace
>>>>>>>>>>>> output you've shown. There are HUGE gaps in your trace!!
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Mike.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Unless we maintain a line-of-demarcation between the halt decider
>>>>>>>>>>> and
>>>>>>>>>>> its input pathological self-reference(Olcott 2004) makes the halting
>>>>>>>>>>> problem have undecidable inputs in the same way that the Liar
>>>>>>>>>>> Paradox is
>>>>>>>>>>> neither true nor false.
>>>>>>>>>>>
>>>>>>>>>>> https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ
>>>>>>>>>>>
>>>>>>>>>>> Instead of asking the question: Does the input halt on its input?
>>>>>>>>>>> that is subject to pathological self-reference.
>>>>>>>>>>>
>>>>>>>>>>> We ask the question: Does the execution of the input have to be
>>>>>>>>>>> aborted
>>>>>>>>>>> to prevent its infinite execution?
>>>>>>>>>>>
>>>>>>>>>>> When we ask this latter question then we can ignore all of the
>>>>>>>>>>> conditional branch instructions that are in the halt decider and
>>>>>>>>>>> only
>>>>>>>>>>> pay attention to the ones that are in the input.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> We can indeed ignore the halt decider outer-level trace entries, and
>>>>>>>>>> concentrate on just what the halt decider embedded emulator sees its
>>>>>>>>>> input doing.
>>>>>>>>>
>>>>>>>>> All that I have right now is a DebugTrace() of all the user specified
>>>>>>>>> code. This provides a very obvious basis for a halt decider's correct
>>>>>>>>> halting decision of the H_Hat code specified in this execution trace.
>>>>>>>>>
>>>>>>>>> There will not be an embedded decider because an embedded decider
>>>>>>>>> permits what would seem to causal observers as inconsistent halting
>>>>>>>>> decisions. By not allowing any execution trace data to exist that the
>>>>>>>>> halt decider cannot see then even the apperance of inconsistency
>>>>>>>>> ceases
>>>>>>>>> to exist.
>>>>>>>>
>>>>>>>> There has to be an embedded decider, because that is how the Linz
>>>>>>>> proof specifies H^. When you say "seem to causal [sic] observers as
>>>>>>>> inconsistent halting decisions" that is because the decisions really
>>>>>>>> are inconsistent! You can't magic them to be consistent by making the
>>>>>>>> decider part of the OS. (If that's your plan.)
>>>>>>>
>>>>>>> I do not have to conform to any conventions but this one:
>>>>>>>
>>>>>>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>>>>>>> H.q0 wMw ⊢* H.no if M applied to w would not halt.
>>>>>>>
>>>>>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>>>>>> expresses behavior that is not halting behavior.
>>>>>>>
>>>>>>
>>>>>> Wrong.
>>>>>>
>>>>>> You are talking here about H, whereas I was talking about H^. If you
>>>>>> want to say anything about the Linz proof, you need to talk about H
>>>>>> *and* H^, and H^ must follow the Linz spec for how it relates to H. Duh.
>>>>>
>>>>> Before we can proceed we need to have agreement on this general
>>>>> principle: (It is a mandatory prerequisite).
>>>>>
>>>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>>>> expresses behavior that is not halting behavior.
>>>> That's a bad wording for lots of reasons. If I agree to it as it
>>>> stands, I know you will take that quote and post it all over the
>>>> newsgroup claiming it means something it doesn't. Because that's the
>>>> kind of guy that you are.
>>>>
>>>> However, I'll happily agree to the better worded:
>>>>
>>>> Any input (TMD, DATA) which, when run under a (pure) UTM
>>>> never halts, expresses behaviour that is not halting behaviour.
>>>
>>> I wonder - doesn't the "input" to a Turing Machine simulation also
>>> need an initial head position specification? It is trivial to design a
>>> tape that halts for some initial head positions but not for others.
>>>
>> Yes, the specification of the tape would include the initial position.
>> For some machines, it starts at a physical end of the tape, and the tape
>> only goes on infinitely in one direction. For machines with bidirection
>> tapes, there is a '0' cell which is the starting point.
>
> I like to think of the tape as a pair of stacks plus a head. This does
> provide a clear initial position. But without a specific position how
> can one know which cell the initial cell under the head is? Are we
> assuming that the tape is an array indexed by all integers?
>
I try to think of it as a list that has a first element.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-11-24 23:14 -0500 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) |
| Message-ID | <mSkvH.11027$lP1.9171@fx37.iad> |
| In reply to | #25877 |
On 11/24/20 8:22 PM, dklei...@gmail.com wrote:
> On Tuesday, November 24, 2020 at 12:46:25 PM UTC-8, Richard Damon wrote:
>> On 11/24/20 3:31 PM, dklei...@gmail.com wrote:
>>> On Tuesday, November 24, 2020 at 8:19:46 AM UTC-8, Mike Terry wrote:
>>>> On 24/11/2020 15:51, olcott wrote:
>>>>> On 11/24/2020 9:41 AM, Mike Terry wrote:
>>>>>> On 24/11/2020 04:18, olcott wrote:
>>>>>>> On 11/23/2020 8:53 PM, Mike Terry wrote:
>>>>>>>> On 24/11/2020 00:37, olcott wrote:
>>>>>>>>> On 11/23/2020 5:51 PM, Mike Terry wrote:
>>>>>>>>>> On 23/11/2020 21:29, olcott wrote:
>>>>>>>>>>> On 11/23/2020 3:02 PM, Mike Terry wrote:
>>>>>>>>>>>> On 23/11/2020 01:24, olcott wrote:
>>>>>>>>>>>>> The following shows exactly how the Peter Linz H would correctly
>>>>>>>>>>>>> decide
>>>>>>>>>>>>> halting on the Peter Linz Ĥ. This is fully operational code
>>>>>>>>>>>>> that has
>>>>>>>>>>>>> been executed in the x86utm operating system that I wrote.
>>>>>>>>>>>>>
>>>>>>>>>>>>> To make the Linz counter-example conform to the standard halting
>>>>>>>>>>>>> problem
>>>>>>>>>>>>> counter-examples the input is not copied as it is in Linz.
>>>>>>>>>>>>>
>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>
>>>>>>>>>>>>> x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
>>>>>>>>>>>>> The x86 language is computationally equivalent to a UTM for all
>>>>>>>>>>>>> computations that do not require more memory than is available.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Recursion can be directly simulated by a UTM that simulates its
>>>>>>>>>>>>> own
>>>>>>>>>>>>> Turing machine Description. Infinite recursion would repeat the
>>>>>>>>>>>>> same
>>>>>>>>>>>>> state transitions every time the UTM simulates its own Turing
>>>>>>>>>>>>> machine
>>>>>>>>>>>>> Description.
>>>>>>>>>>>>>
>>>>>>>>>>>>> // Defined at the bottom of page 319 of Linz
>>>>>>>>>>>>> void Ĥ(u32 P)
>>>>>>>>>>>>> {
>>>>>>>>>>>>> u32 Input_Halts = H(P, P);
>>>>>>>>>>>>> if (!Input_Halts)
>>>>>>>>>>>>> HALT
>>>>>>>>>>>>> else
>>>>>>>>>>>>> HERE: goto HERE;
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> int main()
>>>>>>>>>>>>> {
>>>>>>>>>>>>> u32 P = (u32)Ĥ;
>>>>>>>>>>>>> H(P, P);
>>>>>>>>>>>>> HALT;
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Disassembled x86 machine language of the above pair of C
>>>>>>>>>>>>> functions.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Ĥ()
>>>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>>>> [00000508](03) 83c408 add esp,+08
>>>>>>>>>>>>> [0000050b](03) 8945fc mov [ebp-04],eax
>>>>>>>>>>>>> [0000050e](04) 837dfc00 cmp dword [ebp-04],+00
>>>>>>>>>>>>> [00000512](02) 7403 jz 00000517
>>>>>>>>>>>>> [00000514](01) f4 hlt
>>>>>>>>>>>>> [00000515](02) eb02 jmp 00000519
>>>>>>>>>>>>> [00000517](02) ebfe jmp 00000517
>>>>>>>>>>>>> [00000519](02) 8be5 mov esp,ebp
>>>>>>>>>>>>> [0000051b](01) 5d pop ebp
>>>>>>>>>>>>> [0000051c](01) c3 ret
>>>>>>>>>>>>>
>>>>>>>>>>>>> _main()
>>>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>>>> [0000053f](03) 83c408 add esp,+08
>>>>>>>>>>>>> [00000542](01) f4 hlt
>>>>>>>>>>>>> [00000543](02) 8be5 mov esp,ebp
>>>>>>>>>>>>> [00000545](01) 5d pop ebp
>>>>>>>>>>>>> [00000546](01) c3 ret
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Output_Debug_Trace() [00010abc] size(148) capacity(65536)
>>>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>>>> 25 instructions
>>>>>>>>>>>>>
>>>>>>>>>>>>> The above is where the halt decider aborts the whole Ĥ(Ĥ)
>>>>>>>>>>>>> invocation
>>>>>>>>>>>>> sequence because the halt decider detects infinite recursion.
>>>>>>>>>>>>>
>>>>>>>>>>>>> In this case infinite recursion is a function call to the same
>>>>>>>>>>>>> function
>>>>>>>>>>>>> from the same machine address without any conditional branch
>>>>>>>>>>>>> instructions that would terminate this recursion.
>>>>>>>>>>>>
>>>>>>>>>>>> Hey, you're totally CHEATING here. There ARE conditional branch
>>>>>>>>>>>> intstructions, but you've just silently snipped them from the trace
>>>>>>>>>>>> output you've shown. There are HUGE gaps in your trace!!
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Mike.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Unless we maintain a line-of-demarcation between the halt decider
>>>>>>>>>>> and
>>>>>>>>>>> its input pathological self-reference(Olcott 2004) makes the halting
>>>>>>>>>>> problem have undecidable inputs in the same way that the Liar
>>>>>>>>>>> Paradox is
>>>>>>>>>>> neither true nor false.
>>>>>>>>>>>
>>>>>>>>>>> https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ
>>>>>>>>>>>
>>>>>>>>>>> Instead of asking the question: Does the input halt on its input?
>>>>>>>>>>> that is subject to pathological self-reference.
>>>>>>>>>>>
>>>>>>>>>>> We ask the question: Does the execution of the input have to be
>>>>>>>>>>> aborted
>>>>>>>>>>> to prevent its infinite execution?
>>>>>>>>>>>
>>>>>>>>>>> When we ask this latter question then we can ignore all of the
>>>>>>>>>>> conditional branch instructions that are in the halt decider and
>>>>>>>>>>> only
>>>>>>>>>>> pay attention to the ones that are in the input.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> We can indeed ignore the halt decider outer-level trace entries, and
>>>>>>>>>> concentrate on just what the halt decider embedded emulator sees its
>>>>>>>>>> input doing.
>>>>>>>>>
>>>>>>>>> All that I have right now is a DebugTrace() of all the user specified
>>>>>>>>> code. This provides a very obvious basis for a halt decider's correct
>>>>>>>>> halting decision of the H_Hat code specified in this execution trace.
>>>>>>>>>
>>>>>>>>> There will not be an embedded decider because an embedded decider
>>>>>>>>> permits what would seem to causal observers as inconsistent halting
>>>>>>>>> decisions. By not allowing any execution trace data to exist that the
>>>>>>>>> halt decider cannot see then even the apperance of inconsistency
>>>>>>>>> ceases
>>>>>>>>> to exist.
>>>>>>>>
>>>>>>>> There has to be an embedded decider, because that is how the Linz
>>>>>>>> proof specifies H^. When you say "seem to causal [sic] observers as
>>>>>>>> inconsistent halting decisions" that is because the decisions really
>>>>>>>> are inconsistent! You can't magic them to be consistent by making the
>>>>>>>> decider part of the OS. (If that's your plan.)
>>>>>>>
>>>>>>> I do not have to conform to any conventions but this one:
>>>>>>>
>>>>>>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>>>>>>> H.q0 wMw ⊢* H.no if M applied to w would not halt.
>>>>>>>
>>>>>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>>>>>> expresses behavior that is not halting behavior.
>>>>>>>
>>>>>>
>>>>>> Wrong.
>>>>>>
>>>>>> You are talking here about H, whereas I was talking about H^. If you
>>>>>> want to say anything about the Linz proof, you need to talk about H
>>>>>> *and* H^, and H^ must follow the Linz spec for how it relates to H. Duh.
>>>>>
>>>>> Before we can proceed we need to have agreement on this general
>>>>> principle: (It is a mandatory prerequisite).
>>>>>
>>>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>>>> expresses behavior that is not halting behavior.
>>>> That's a bad wording for lots of reasons. If I agree to it as it
>>>> stands, I know you will take that quote and post it all over the
>>>> newsgroup claiming it means something it doesn't. Because that's the
>>>> kind of guy that you are.
>>>>
>>>> However, I'll happily agree to the better worded:
>>>>
>>>> Any input (TMD, DATA) which, when run under a (pure) UTM
>>>> never halts, expresses behaviour that is not halting behaviour.
>>>
>>> I wonder - doesn't the "input" to a Turing Machine simulation also
>>> need an initial head position specification? It is trivial to design a
>>> tape that halts for some initial head positions but not for others.
>>>
>> Yes, the specification of the tape would include the initial position.
>> For some machines, it starts at a physical end of the tape, and the tape
>> only goes on infinitely in one direction. For machines with bidirection
>> tapes, there is a '0' cell which is the starting point.
>
> I like to think of the tape as a pair of stacks plus a head. This does
> provide a clear initial position. But without a specific position how
> can one know which cell the initial cell under the head is? Are we
> assuming that the tape is an array indexed by all integers?
As I said, for some machines, the tape is single directional, with a
normal default of starting at the end.
For other cases, the tape is specified relative to the head. One way to
do this is to provide index numbers, another is to just list them with
an indicated (or implied) position for the head.
>
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-24 14:48 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](mandatory prerequisite) |
| Message-ID | <fuqdndEstY4d7CDCnZ2dnUU7-K_NnZ2d@giganews.com> |
| In reply to | #25829 |
On 11/24/2020 2:31 PM, dklei...@gmail.com wrote:
> On Tuesday, November 24, 2020 at 8:19:46 AM UTC-8, Mike Terry wrote:
>> On 24/11/2020 15:51, olcott wrote:
>>> On 11/24/2020 9:41 AM, Mike Terry wrote:
>>>> On 24/11/2020 04:18, olcott wrote:
>>>>> On 11/23/2020 8:53 PM, Mike Terry wrote:
>>>>>> On 24/11/2020 00:37, olcott wrote:
>>>>>>> On 11/23/2020 5:51 PM, Mike Terry wrote:
>>>>>>>> On 23/11/2020 21:29, olcott wrote:
>>>>>>>>> On 11/23/2020 3:02 PM, Mike Terry wrote:
>>>>>>>>>> On 23/11/2020 01:24, olcott wrote:
>>>>>>>>>>> The following shows exactly how the Peter Linz H would correctly
>>>>>>>>>>> decide
>>>>>>>>>>> halting on the Peter Linz Ĥ. This is fully operational code
>>>>>>>>>>> that has
>>>>>>>>>>> been executed in the x86utm operating system that I wrote.
>>>>>>>>>>>
>>>>>>>>>>> To make the Linz counter-example conform to the standard halting
>>>>>>>>>>> problem
>>>>>>>>>>> counter-examples the input is not copied as it is in Linz.
>>>>>>>>>>>
>>>>>>>>>>> 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.
>>>>>>>>>>>
>>>>>>>>>>> x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
>>>>>>>>>>> The x86 language is computationally equivalent to a UTM for all
>>>>>>>>>>> computations that do not require more memory than is available.
>>>>>>>>>>>
>>>>>>>>>>> Recursion can be directly simulated by a UTM that simulates its
>>>>>>>>>>> own
>>>>>>>>>>> Turing machine Description. Infinite recursion would repeat the
>>>>>>>>>>> same
>>>>>>>>>>> state transitions every time the UTM simulates its own Turing
>>>>>>>>>>> machine
>>>>>>>>>>> Description.
>>>>>>>>>>>
>>>>>>>>>>> // Defined at the bottom of page 319 of Linz
>>>>>>>>>>> void Ĥ(u32 P)
>>>>>>>>>>> {
>>>>>>>>>>> u32 Input_Halts = H(P, P);
>>>>>>>>>>> if (!Input_Halts)
>>>>>>>>>>> HALT
>>>>>>>>>>> else
>>>>>>>>>>> HERE: goto HERE;
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> int main()
>>>>>>>>>>> {
>>>>>>>>>>> u32 P = (u32)Ĥ;
>>>>>>>>>>> H(P, P);
>>>>>>>>>>> HALT;
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Disassembled x86 machine language of the above pair of C
>>>>>>>>>>> functions.
>>>>>>>>>>>
>>>>>>>>>>> Ĥ()
>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>> [00000508](03) 83c408 add esp,+08
>>>>>>>>>>> [0000050b](03) 8945fc mov [ebp-04],eax
>>>>>>>>>>> [0000050e](04) 837dfc00 cmp dword [ebp-04],+00
>>>>>>>>>>> [00000512](02) 7403 jz 00000517
>>>>>>>>>>> [00000514](01) f4 hlt
>>>>>>>>>>> [00000515](02) eb02 jmp 00000519
>>>>>>>>>>> [00000517](02) ebfe jmp 00000517
>>>>>>>>>>> [00000519](02) 8be5 mov esp,ebp
>>>>>>>>>>> [0000051b](01) 5d pop ebp
>>>>>>>>>>> [0000051c](01) c3 ret
>>>>>>>>>>>
>>>>>>>>>>> _main()
>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>> [0000053f](03) 83c408 add esp,+08
>>>>>>>>>>> [00000542](01) f4 hlt
>>>>>>>>>>> [00000543](02) 8be5 mov esp,ebp
>>>>>>>>>>> [00000545](01) 5d pop ebp
>>>>>>>>>>> [00000546](01) c3 ret
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Output_Debug_Trace() [00010abc] size(148) capacity(65536)
>>>>>>>>>>> [00000527](01) 55 push ebp
>>>>>>>>>>> [00000528](02) 8bec mov ebp,esp
>>>>>>>>>>> [0000052a](01) 51 push ecx
>>>>>>>>>>> [0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
>>>>>>>>>>> [00000532](03) 8b45fc mov eax,[ebp-04]
>>>>>>>>>>> [00000535](01) 50 push eax
>>>>>>>>>>> [00000536](03) 8b4dfc mov ecx,[ebp-04]
>>>>>>>>>>> [00000539](01) 51 push ecx
>>>>>>>>>>> [0000053a](05) e838feffff call 00000377
>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>> [000004f7](01) 55 push ebp
>>>>>>>>>>> [000004f8](02) 8bec mov ebp,esp
>>>>>>>>>>> [000004fa](01) 51 push ecx
>>>>>>>>>>> [000004fb](03) 8b4508 mov eax,[ebp+08]
>>>>>>>>>>> [000004fe](01) 50 push eax
>>>>>>>>>>> [000004ff](03) 8b4d08 mov ecx,[ebp+08]
>>>>>>>>>>> [00000502](01) 51 push ecx
>>>>>>>>>>> [00000503](05) e86ffeffff call 00000377
>>>>>>>>>>> 25 instructions
>>>>>>>>>>>
>>>>>>>>>>> The above is where the halt decider aborts the whole Ĥ(Ĥ)
>>>>>>>>>>> invocation
>>>>>>>>>>> sequence because the halt decider detects infinite recursion.
>>>>>>>>>>>
>>>>>>>>>>> In this case infinite recursion is a function call to the same
>>>>>>>>>>> function
>>>>>>>>>>> from the same machine address without any conditional branch
>>>>>>>>>>> instructions that would terminate this recursion.
>>>>>>>>>>
>>>>>>>>>> Hey, you're totally CHEATING here. There ARE conditional branch
>>>>>>>>>> intstructions, but you've just silently snipped them from the trace
>>>>>>>>>> output you've shown. There are HUGE gaps in your trace!!
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Mike.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Unless we maintain a line-of-demarcation between the halt decider
>>>>>>>>> and
>>>>>>>>> its input pathological self-reference(Olcott 2004) makes the halting
>>>>>>>>> problem have undecidable inputs in the same way that the Liar
>>>>>>>>> Paradox is
>>>>>>>>> neither true nor false.
>>>>>>>>>
>>>>>>>>> https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ
>>>>>>>>>
>>>>>>>>> Instead of asking the question: Does the input halt on its input?
>>>>>>>>> that is subject to pathological self-reference.
>>>>>>>>>
>>>>>>>>> We ask the question: Does the execution of the input have to be
>>>>>>>>> aborted
>>>>>>>>> to prevent its infinite execution?
>>>>>>>>>
>>>>>>>>> When we ask this latter question then we can ignore all of the
>>>>>>>>> conditional branch instructions that are in the halt decider and
>>>>>>>>> only
>>>>>>>>> pay attention to the ones that are in the input.
>>>>>>>>>
>>>>>>>>
>>>>>>>> We can indeed ignore the halt decider outer-level trace entries, and
>>>>>>>> concentrate on just what the halt decider embedded emulator sees its
>>>>>>>> input doing.
>>>>>>>
>>>>>>> All that I have right now is a DebugTrace() of all the user specified
>>>>>>> code. This provides a very obvious basis for a halt decider's correct
>>>>>>> halting decision of the H_Hat code specified in this execution trace.
>>>>>>>
>>>>>>> There will not be an embedded decider because an embedded decider
>>>>>>> permits what would seem to causal observers as inconsistent halting
>>>>>>> decisions. By not allowing any execution trace data to exist that the
>>>>>>> halt decider cannot see then even the apperance of inconsistency
>>>>>>> ceases
>>>>>>> to exist.
>>>>>>
>>>>>> There has to be an embedded decider, because that is how the Linz
>>>>>> proof specifies H^. When you say "seem to causal [sic] observers as
>>>>>> inconsistent halting decisions" that is because the decisions really
>>>>>> are inconsistent! You can't magic them to be consistent by making the
>>>>>> decider part of the OS. (If that's your plan.)
>>>>>
>>>>> I do not have to conform to any conventions but this one:
>>>>>
>>>>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>>>>> H.q0 wMw ⊢* H.no if M applied to w would not halt.
>>>>>
>>>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>>>> expresses behavior that is not halting behavior.
>>>>>
>>>>
>>>> Wrong.
>>>>
>>>> You are talking here about H, whereas I was talking about H^. If you
>>>> want to say anything about the Linz proof, you need to talk about H
>>>> *and* H^, and H^ must follow the Linz spec for how it relates to H. Duh.
>>>
>>> Before we can proceed we need to have agreement on this general
>>> principle: (It is a mandatory prerequisite).
>>>
>>> Any input TMD that would never halt unless a UTM stopped simulating it
>>> expresses behavior that is not halting behavior.
>> That's a bad wording for lots of reasons. If I agree to it as it
>> stands, I know you will take that quote and post it all over the
>> newsgroup claiming it means something it doesn't. Because that's the
>> kind of guy that you are.
>>
>> However, I'll happily agree to the better worded:
>>
>> Any input (TMD, DATA) which, when run under a (pure) UTM
>> never halts, expresses behaviour that is not halting behaviour.
>
> I wonder - doesn't the "input" to a Turing Machine simulation also
> need an initial head position specification? It is trivial to design a
> tape that halts for some initial head positions but not for others.
I think that most people assume that the initial tape head position for
a UTM's input is the beginning of its tape for tapes that are boundless
in one direction.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-25 16:45 +0000 |
| Message-ID | <qPCdnSYYdNW-FyPCnZ2dnUU78QHNnZ2d@brightview.co.uk> |
| In reply to | #25798 |
On 24/11/2020 15:41, Mike Terry wrote: > On 24/11/2020 04:18, olcott wrote: <.. snip ..> >> >> People can eventually look at all of my code and the thousands of lines >> of code of the x86 emulator and they can look at the hundreds of pages >> out output. It all boils down to this: >> >> The simulator merely watches its simulation of the following >> instructions until it sees a function call to 377 from 503 the second >> time with no JCC (Jump-Condition_Code) in-between. >> > > I have told you many times that your test must be UNSOUND. You have > never responded to this, so I've assumed you don't really know whether > your test is sound or unsound (or probably, what that even means, > although I've also explained that to you before). > > Now you are getting closer to actually coding the test (which you > claimed to have "fully coded" two years ago), you are finally giving > more details. > > So... what do you think. Is the following test a SOUND test for > non-halting? > > TEST: "monitor the simulation until there is a function > call to 377 from 503 a second time, with no conditional > branch inbetween" > > Putting it more directly - if some calculation P(I) triggers the TEST > (so it contains two calls from 377 from 503, with no conditional branch > inbetween), does this genuinely imply that the calculation will never halt? > > Bear in mind that the two calls in question do not necessarily occur in > the same "virtual address space", that is to say the two calls can [and > in the case of T_Hat(T_Hat) *do* ] occur at /different levels of > emulation/. [Your trace notation obscures this simple fact, making > everything appear to be in one single virtual process, when it's not.] > > What do you think? This seems to be your primary intuition that > triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT? > > Of course, you will say "All my intuitions are correct by definition - > I'm never wrong" but that doesn't make it true! :) > > Is TEST *SOUND* ? > Noted: still no response to this basic question. Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-25 11:21 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](infallible) |
| Message-ID | <EOudnWsbKL0RDyPCnZ2dnUU7-SudnZ2d@giganews.com> |
| In reply to | #25945 |
On 11/25/2020 10:45 AM, Mike Terry wrote:
> On 24/11/2020 15:41, Mike Terry wrote:
>> On 24/11/2020 04:18, olcott wrote:
> <.. snip ..>
>>>
>>> People can eventually look at all of my code and the thousands of lines
>>> of code of the x86 emulator and they can look at the hundreds of pages
>>> out output. It all boils down to this:
>>>
>>> The simulator merely watches its simulation of the following
>>> instructions until it sees a function call to 377 from 503 the second
>>> time with no JCC (Jump-Condition_Code) in-between.
>>>
>>
>> I have told you many times that your test must be UNSOUND. You have
>> never responded to this, so I've assumed you don't really know whether
>> your test is sound or unsound (or probably, what that even means,
>> although I've also explained that to you before).
>>
>> Now you are getting closer to actually coding the test (which you
>> claimed to have "fully coded" two years ago), you are finally giving
>> more details.
>>
>> So... what do you think. Is the following test a SOUND test for
>> non-halting?
>>
>> TEST: "monitor the simulation until there is a function
>> call to 377 from 503 a second time, with no conditional
>> branch inbetween"
>>
>> Putting it more directly - if some calculation P(I) triggers the TEST
>> (so it contains two calls from 377 from 503, with no conditional branch
>> inbetween), does this genuinely imply that the calculation will never
>> halt?
>>
>> Bear in mind that the two calls in question do not necessarily occur in
>> the same "virtual address space", that is to say the two calls can [and
>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of
>> emulation/. [Your trace notation obscures this simple fact, making
>> everything appear to be in one single virtual process, when it's not.]
>>
>> What do you think? This seems to be your primary intuition that
>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT?
>>
>> Of course, you will say "All my intuitions are correct by definition -
>> I'm never wrong" but that doesn't make it true! :)
>>
>> Is TEST *SOUND* ?
>>
>
> Noted: still no response to this basic question.
>
> Mike.
>
int DebugTrace(u32 N, u32 M)
{
return ((int(*)(int))N)(M);
}
void H_Hat(u32 P)
{
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
int main()
{
u32 P = (u32)H_Hat;
DebugTrace(P, P);
HALT;
}
The determination that the above code specifies infinite recursion is
infallible. People can have different meanings for the term "sound",
infallible has only one meaning.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-25 21:25 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](infallible) |
| Message-ID | <M-GdnWrECtIvViPCnZ2dnUU78c_NnZ2d@brightview.co.uk> |
| In reply to | #25947 |
On 25/11/2020 17:21, olcott wrote:
> On 11/25/2020 10:45 AM, Mike Terry wrote:
>> On 24/11/2020 15:41, Mike Terry wrote:
>>> On 24/11/2020 04:18, olcott wrote:
>> <.. snip ..>
>>>>
>>>> People can eventually look at all of my code and the thousands of lines
>>>> of code of the x86 emulator and they can look at the hundreds of pages
>>>> out output. It all boils down to this:
>>>>
>>>> The simulator merely watches its simulation of the following
>>>> instructions until it sees a function call to 377 from 503 the second
>>>> time with no JCC (Jump-Condition_Code) in-between.
>>>>
>>>
>>> I have told you many times that your test must be UNSOUND. You have
>>> never responded to this, so I've assumed you don't really know whether
>>> your test is sound or unsound (or probably, what that even means,
>>> although I've also explained that to you before).
>>>
>>> Now you are getting closer to actually coding the test (which you
>>> claimed to have "fully coded" two years ago), you are finally giving
>>> more details.
>>>
>>> So... what do you think. Is the following test a SOUND test for
>>> non-halting?
>>>
>>> TEST: "monitor the simulation until there is a function
>>> call to 377 from 503 a second time, with no conditional
>>> branch inbetween"
>>>
>>> Putting it more directly - if some calculation P(I) triggers the TEST
>>> (so it contains two calls from 377 from 503, with no conditional branch
>>> inbetween), does this genuinely imply that the calculation will never
>>> halt?
>>>
>>> Bear in mind that the two calls in question do not necessarily occur in
>>> the same "virtual address space", that is to say the two calls can [and
>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of
>>> emulation/. [Your trace notation obscures this simple fact, making
>>> everything appear to be in one single virtual process, when it's not.]
>>>
>>> What do you think? This seems to be your primary intuition that
>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT?
>>>
>>> Of course, you will say "All my intuitions are correct by definition -
>>> I'm never wrong" but that doesn't make it true! :)
>>>
>>> Is TEST *SOUND* ?
>>>
>>
>> Noted: still no response to this basic question.
>>
>> Mike.
>>
<.. snip non-response to question ..>
I'm not sure if that non-response was deliberate. I didn't ask whether
one specified implementation of [whatever] exhibits infinite recursion!
In case it was just a misreading, here is the question again.
So... what do you think. Is the following test a SOUND test for
non-halting?
TEST: "monitor the simulation until there is a function
call to 377 from 503 a second time, with no conditional
branch in-between"
Putting it more directly - if some calculation P(I) triggers
the TEST (so it contains two calls from 377 from 503, with no
conditional branch in-between), does this genuinely imply that
the calculation will never halt?
The context for this is that TEST is what you've claimed to be the test
within your emulation single-step loop that you use to break the loop,
determining that the input (P,I) is non-halting.
If you don't like the word "sound" just ignore that word, and read the
"putting it more directly" paragraph equivalent wording!
Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-25 15:55 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <ZridnafptIUjTyPCnZ2dnUU7-UXNnZ2d@giganews.com> |
| In reply to | #25968 |
On 11/25/2020 3:25 PM, Mike Terry wrote: > On 25/11/2020 17:21, olcott wrote: >> On 11/25/2020 10:45 AM, Mike Terry wrote: >>> On 24/11/2020 15:41, Mike Terry wrote: >>>> On 24/11/2020 04:18, olcott wrote: >>> <.. snip ..> >>>>> >>>>> People can eventually look at all of my code and the thousands of >>>>> lines >>>>> of code of the x86 emulator and they can look at the hundreds of pages >>>>> out output. It all boils down to this: >>>>> >>>>> The simulator merely watches its simulation of the following >>>>> instructions until it sees a function call to 377 from 503 the second >>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>> >>>> >>>> I have told you many times that your test must be UNSOUND. You have >>>> never responded to this, so I've assumed you don't really know whether >>>> your test is sound or unsound (or probably, what that even means, >>>> although I've also explained that to you before). >>>> >>>> Now you are getting closer to actually coding the test (which you >>>> claimed to have "fully coded" two years ago), you are finally giving >>>> more details. >>>> >>>> So... what do you think. Is the following test a SOUND test for >>>> non-halting? >>>> >>>> TEST: "monitor the simulation until there is a function >>>> call to 377 from 503 a second time, with no conditional >>>> branch inbetween" >>>> >>>> Putting it more directly - if some calculation P(I) triggers the TEST >>>> (so it contains two calls from 377 from 503, with no conditional branch >>>> inbetween), does this genuinely imply that the calculation will never >>>> halt? >>>> >>>> Bear in mind that the two calls in question do not necessarily occur in >>>> the same "virtual address space", that is to say the two calls can [and >>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of >>>> emulation/. [Your trace notation obscures this simple fact, making >>>> everything appear to be in one single virtual process, when it's not.] >>>> >>>> What do you think? This seems to be your primary intuition that >>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT? >>>> >>>> Of course, you will say "All my intuitions are correct by definition - >>>> I'm never wrong" but that doesn't make it true! :) >>>> >>>> Is TEST *SOUND* ? >>>> >>> >>> Noted: still no response to this basic question. >>> >>> Mike. >>> > <.. snip non-response to question ..> > > I'm not sure if that non-response was deliberate. I didn't ask whether > one specified implementation of [whatever] exhibits infinite recursion! > > In case it was just a misreading, here is the question again. > > > So... what do you think. Is the following test a SOUND test for > non-halting? > > TEST: "monitor the simulation until there is a function > call to 377 from 503 a second time, with no conditional > branch in-between" It is much more generic than that. (1) Keep a global execution trace of every line of user code. (2) Whenever any instruction is executed see if it is a function call. (3) If it is a function call find the prior call to this same function from the current machine address (if any) searching backward through the global execution trace and counting conditional branch instructions. (4) If found and conditional-branch-count == zero terminate the input. Copyright 2020 Pete Olcott (I just wrote that algorithm right now). I had been postponing this fun task until I had the tedious task of decoding the machine language of all control flow instructions completed > Putting it more directly - if some calculation P(I) triggers > the TEST (so it contains two calls from 377 from 503, with no > conditional branch in-between), does this genuinely imply that > the calculation will never halt? > > The context for this is that TEST is what you've claimed to be the test > within your emulation single-step loop that you use to break the loop, > determining that the input (P,I) is non-halting. > > If you don't like the word "sound" just ignore that word, and read the > "putting it more directly" paragraph equivalent wording! > > > Mike. > I like impossibly incorrect the best. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-25 23:31 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <zIudnVpmqcfEdCPCnZ2dnUU78aOdnZ2d@brightview.co.uk> |
| In reply to | #25973 |
On 25/11/2020 21:55, olcott wrote:
> On 11/25/2020 3:25 PM, Mike Terry wrote:
>> On 25/11/2020 17:21, olcott wrote:
>>> On 11/25/2020 10:45 AM, Mike Terry wrote:
>>>> On 24/11/2020 15:41, Mike Terry wrote:
>>>>> On 24/11/2020 04:18, olcott wrote:
>>>> <.. snip ..>
>>>>>>
>>>>>> People can eventually look at all of my code and the thousands of
>>>>>> lines
>>>>>> of code of the x86 emulator and they can look at the hundreds of
>>>>>> pages
>>>>>> out output. It all boils down to this:
>>>>>>
>>>>>> The simulator merely watches its simulation of the following
>>>>>> instructions until it sees a function call to 377 from 503 the second
>>>>>> time with no JCC (Jump-Condition_Code) in-between.
>>>>>>
>>>>>
>>>>> I have told you many times that your test must be UNSOUND. You have
>>>>> never responded to this, so I've assumed you don't really know whether
>>>>> your test is sound or unsound (or probably, what that even means,
>>>>> although I've also explained that to you before).
>>>>>
>>>>> Now you are getting closer to actually coding the test (which you
>>>>> claimed to have "fully coded" two years ago), you are finally giving
>>>>> more details.
>>>>>
>>>>> So... what do you think. Is the following test a SOUND test for
>>>>> non-halting?
>>>>>
>>>>> TEST: "monitor the simulation until there is a function
>>>>> call to 377 from 503 a second time, with no conditional
>>>>> branch inbetween"
>>>>>
>>>>> Putting it more directly - if some calculation P(I) triggers the TEST
>>>>> (so it contains two calls from 377 from 503, with no conditional
>>>>> branch
>>>>> inbetween), does this genuinely imply that the calculation will never
>>>>> halt?
>>>>>
>>>>> Bear in mind that the two calls in question do not necessarily
>>>>> occur in
>>>>> the same "virtual address space", that is to say the two calls can
>>>>> [and
>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of
>>>>> emulation/. [Your trace notation obscures this simple fact, making
>>>>> everything appear to be in one single virtual process, when it's not.]
>>>>>
>>>>> What do you think? This seems to be your primary intuition that
>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT?
>>>>>
>>>>> Of course, you will say "All my intuitions are correct by definition -
>>>>> I'm never wrong" but that doesn't make it true! :)
>>>>>
>>>>> Is TEST *SOUND* ?
>>>>>
>>>>
>>>> Noted: still no response to this basic question.
>>>>
>>>> Mike.
>>>>
>> <.. snip non-response to question ..>
>>
>> I'm not sure if that non-response was deliberate. I didn't ask
>> whether one specified implementation of [whatever] exhibits infinite
>> recursion!
>>
>> In case it was just a misreading, here is the question again.
>>
>>
>> So... what do you think. Is the following test a SOUND test for
>> non-halting?
>>
>> TEST: "monitor the simulation until there is a function
>> call to 377 from 503 a second time, with no conditional
>> branch in-between"
>
> It is much more generic than that.
> (1) Keep a global execution trace of every line of user code.
>
> (2) Whenever any instruction is executed see if it is a function call.
>
> (3) If it is a function call find the prior call to this same function
> from the current machine address (if any) searching backward through the
> global execution trace and counting conditional branch instructions.
>
> (4) If found and conditional-branch-count == zero terminate the input.
>
> Copyright 2020 Pete Olcott (I just wrote that algorithm right now).
OK, I always imagined the test would be more general than just checking
specifically for calls to 377 from 503. :) No problem on that front.
I'm thinking this is probably the basis of your initial intuition that
you could actually detect and handle the type of recursion in your
fledgeling (at that time) halt decider design.
It is good that you've clarified the test, and yet it seems you're
reluctant to plainly say that you believe the test works!
For example, in (4) you say
"[if TEST matches] terminate the input",
whereas you could just as easily have said
"[if TEST matches] terminate the input, *because the
detected condition implies that the input calculation
never halts*".
What if you correctly detect the condition you describe, but that
condition doesn't imply that the examined input is actually exhibiting
infinite recursive emulation? (Maybe it later breaks out, or whatever,
exactly how doesn't matter right now...)
Do you see the point I'm making? You've clarified the test, and I
strongly suspect you /do/ believe that if that test matches when
examining a trace, then IT FOLLOWS that the calculation being examined
is infinitely recursive, but you never actually say this!
Why not actually say it and be clear? Or do you consider that you have
said it by implication, so why am I chasing you like this?
Or do you consider that the test /doesn't/ imply anything about the
halting/non-halting nature of the examined input? Or what? (Maybe if
your test matches, that means the calculation being examined has a 0.92
probability that it is never going to halt, so it's fair to say the
input /probably/ never halts...)
-----------------------
To give two contrasting tests, to show why I keep asking:
A good example:
1) Check if current instruction is an unconditional branch to
a fixed address (not indirect addressing)
2) Check if target of branch is the current branch instruction
3) If it is, TERMINATE THE EMULATION and return false.
*Claim*: If this test matches, THEN IT FOLLOWS that the examined
calculation has gone into a tight loop. THEREFORE THE CALCULATION WILL
NEVER HALT. [This is the paragraph which is missing from your posts.]
Next a POOR test:
1) Check if current instruction is NOP
2) If it is, TERMINATE THE EMULATION and return false.
*Claim*: [ *Um, No claim given* !!]
OK, that's worded in similar fashion to your wording: the test is
properly described, and what to do (terminate emulation) is described,
but no claim is made [whether correct or incorrect] stating that the
test "works" - so program behaviour is properly described but we can't
reason that because the emulation was terminated by the test, the input
calculation never halts. [It could be argued that there's nothing wrong
with this test - it does what it says on the tin! But in the larger
picture we want to be able to /reason/ about the program behaviour going
beyond "emulation halted because the test told it to" - we actually want
to say "we know the calculation is non-halting because the test matched,
and the test works (i.e. is sound)." :) ]
And sure enough, if we terminated an emulation because we found a NOP
(no-operation) that /doesn't/ mean the calculation is never going to
halt... (Still, it's true to say, I guess, that the test matched, and
the emulation was halted so there's "no contradiction". That's pretty
useless though.)
Mike.
>
> I had been postponing this fun task until I had the tedious task of
> decoding the machine language of all control flow instructions completed
>
>> Putting it more directly - if some calculation P(I) triggers
>> the TEST (so it contains two calls from 377 from 503, with no
>> conditional branch in-between), does this genuinely imply that
>> the calculation will never halt?
>>
>> The context for this is that TEST is what you've claimed to be the
>> test within your emulation single-step loop that you use to break the
>> loop, determining that the input (P,I) is non-halting.
>>
>> If you don't like the word "sound" just ignore that word, and read the
>> "putting it more directly" paragraph equivalent wording!
>>
>>
>> Mike.
>>
>
> I like impossibly incorrect the best.
(To me, that sounds like a crank/duffer phrasing...)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-25 17:47 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <_PidnS5eJ9eLcCPCnZ2dnUU7-LfNnZ2d@giganews.com> |
| In reply to | #25982 |
On 11/25/2020 5:31 PM, Mike Terry wrote: > On 25/11/2020 21:55, olcott wrote: >> On 11/25/2020 3:25 PM, Mike Terry wrote: >>> On 25/11/2020 17:21, olcott wrote: >>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>> On 24/11/2020 04:18, olcott wrote: >>>>> <.. snip ..> >>>>>>> >>>>>>> People can eventually look at all of my code and the thousands of >>>>>>> lines >>>>>>> of code of the x86 emulator and they can look at the hundreds of >>>>>>> pages >>>>>>> out output. It all boils down to this: >>>>>>> >>>>>>> The simulator merely watches its simulation of the following >>>>>>> instructions until it sees a function call to 377 from 503 the >>>>>>> second >>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>> >>>>>> >>>>>> I have told you many times that your test must be UNSOUND. You have >>>>>> never responded to this, so I've assumed you don't really know >>>>>> whether >>>>>> your test is sound or unsound (or probably, what that even means, >>>>>> although I've also explained that to you before). >>>>>> >>>>>> Now you are getting closer to actually coding the test (which you >>>>>> claimed to have "fully coded" two years ago), you are finally giving >>>>>> more details. >>>>>> >>>>>> So... what do you think. Is the following test a SOUND test for >>>>>> non-halting? >>>>>> >>>>>> TEST: "monitor the simulation until there is a function >>>>>> call to 377 from 503 a second time, with no conditional >>>>>> branch inbetween" >>>>>> >>>>>> Putting it more directly - if some calculation P(I) triggers the TEST >>>>>> (so it contains two calls from 377 from 503, with no conditional >>>>>> branch >>>>>> inbetween), does this genuinely imply that the calculation will never >>>>>> halt? >>>>>> >>>>>> Bear in mind that the two calls in question do not necessarily >>>>>> occur in >>>>>> the same "virtual address space", that is to say the two calls can >>>>>> [and >>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of >>>>>> emulation/. [Your trace notation obscures this simple fact, making >>>>>> everything appear to be in one single virtual process, when it's >>>>>> not.] >>>>>> >>>>>> What do you think? This seems to be your primary intuition that >>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT? >>>>>> >>>>>> Of course, you will say "All my intuitions are correct by >>>>>> definition - >>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>> >>>>>> Is TEST *SOUND* ? >>>>>> >>>>> >>>>> Noted: still no response to this basic question. >>>>> >>>>> Mike. >>>>> >>> <.. snip non-response to question ..> >>> >>> I'm not sure if that non-response was deliberate. I didn't ask >>> whether one specified implementation of [whatever] exhibits infinite >>> recursion! >>> >>> In case it was just a misreading, here is the question again. >>> >>> >>> So... what do you think. Is the following test a SOUND test for >>> non-halting? >>> >>> TEST: "monitor the simulation until there is a function >>> call to 377 from 503 a second time, with no conditional >>> branch in-between" >> >> It is much more generic than that. >> (1) Keep a global execution trace of every line of user code. >> >> (2) Whenever any instruction is executed see if it is a function call. >> >> (3) If it is a function call find the prior call to this same function >> from the current machine address (if any) searching backward through the >> global execution trace and counting conditional branch instructions. >> >> (4) If found and conditional-branch-count == zero terminate the input. >> >> Copyright 2020 Pete Olcott (I just wrote that algorithm right now). > > OK, I always imagined the test would be more general than just checking > specifically for calls to 377 from 503. :) No problem on that front. > > I'm thinking this is probably the basis of your initial intuition that > you could actually detect and handle the type of recursion in your > fledgeling (at that time) halt decider design. > > It is good that you've clarified the test, and yet it seems you're > reluctant to plainly say that you believe the test works! logical necessity speaks for itself it doesn't need me for a cheerleader. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-26 00:33 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <Iqmdnbz55_xraiPCnZ2dnUU78V-dnZ2d@brightview.co.uk> |
| In reply to | #25984 |
On 25/11/2020 23:47, olcott wrote: > On 11/25/2020 5:31 PM, Mike Terry wrote: >> On 25/11/2020 21:55, olcott wrote: >>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>> On 25/11/2020 17:21, olcott wrote: >>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>> <.. snip ..> >>>>>>>> >>>>>>>> People can eventually look at all of my code and the thousands of >>>>>>>> lines >>>>>>>> of code of the x86 emulator and they can look at the hundreds of >>>>>>>> pages >>>>>>>> out output. It all boils down to this: >>>>>>>> >>>>>>>> The simulator merely watches its simulation of the following >>>>>>>> instructions until it sees a function call to 377 from 503 the >>>>>>>> second >>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>> >>>>>>> >>>>>>> I have told you many times that your test must be UNSOUND. You have >>>>>>> never responded to this, so I've assumed you don't really know >>>>>>> whether >>>>>>> your test is sound or unsound (or probably, what that even means, >>>>>>> although I've also explained that to you before). >>>>>>> >>>>>>> Now you are getting closer to actually coding the test (which you >>>>>>> claimed to have "fully coded" two years ago), you are finally giving >>>>>>> more details. >>>>>>> >>>>>>> So... what do you think. Is the following test a SOUND test for >>>>>>> non-halting? >>>>>>> >>>>>>> TEST: "monitor the simulation until there is a function >>>>>>> call to 377 from 503 a second time, with no conditional >>>>>>> branch inbetween" >>>>>>> >>>>>>> Putting it more directly - if some calculation P(I) triggers the >>>>>>> TEST >>>>>>> (so it contains two calls from 377 from 503, with no conditional >>>>>>> branch >>>>>>> inbetween), does this genuinely imply that the calculation will >>>>>>> never >>>>>>> halt? >>>>>>> >>>>>>> Bear in mind that the two calls in question do not necessarily >>>>>>> occur in >>>>>>> the same "virtual address space", that is to say the two calls can >>>>>>> [and >>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of >>>>>>> emulation/. [Your trace notation obscures this simple fact, making >>>>>>> everything appear to be in one single virtual process, when it's >>>>>>> not.] >>>>>>> >>>>>>> What do you think? This seems to be your primary intuition that >>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT? >>>>>>> >>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>> definition - >>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>> >>>>>>> Is TEST *SOUND* ? >>>>>>> >>>>>> >>>>>> Noted: still no response to this basic question. >>>>>> >>>>>> Mike. >>>>>> >>>> <.. snip non-response to question ..> >>>> >>>> I'm not sure if that non-response was deliberate. I didn't ask >>>> whether one specified implementation of [whatever] exhibits infinite >>>> recursion! >>>> >>>> In case it was just a misreading, here is the question again. >>>> >>>> >>>> So... what do you think. Is the following test a SOUND test for >>>> non-halting? >>>> >>>> TEST: "monitor the simulation until there is a function >>>> call to 377 from 503 a second time, with no conditional >>>> branch in-between" >>> >>> It is much more generic than that. >>> (1) Keep a global execution trace of every line of user code. >>> >>> (2) Whenever any instruction is executed see if it is a function call. >>> >>> (3) If it is a function call find the prior call to this same function >>> from the current machine address (if any) searching backward through the >>> global execution trace and counting conditional branch instructions. >>> >>> (4) If found and conditional-branch-count == zero terminate the input. >>> >>> Copyright 2020 Pete Olcott (I just wrote that algorithm right now). >> >> OK, I always imagined the test would be more general than just >> checking specifically for calls to 377 from 503. :) No problem on >> that front. >> >> I'm thinking this is probably the basis of your initial intuition that >> you could actually detect and handle the type of recursion in your >> fledgeling (at that time) halt decider design. >> >> It is good that you've clarified the test, and yet it seems you're >> reluctant to plainly say that you believe the test works! > > logical necessity speaks for itself it doesn't need me for a cheerleader. > LOL. I knew you'd do something like that. OK, so you are saying that if your test detects the behaviour described, then it's a "logical necessity" that the input being examined is non-halting?
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-25 18:51 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <zf6dnTkZ6Pi-YSPCnZ2dnUU7-TudnZ2d@giganews.com> |
| In reply to | #25989 |
On 11/25/2020 6:33 PM, Mike Terry wrote: > On 25/11/2020 23:47, olcott wrote: >> On 11/25/2020 5:31 PM, Mike Terry wrote: >>> On 25/11/2020 21:55, olcott wrote: >>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>> On 25/11/2020 17:21, olcott wrote: >>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>> <.. snip ..> >>>>>>>>> >>>>>>>>> People can eventually look at all of my code and the thousands of >>>>>>>>> lines >>>>>>>>> of code of the x86 emulator and they can look at the hundreds of >>>>>>>>> pages >>>>>>>>> out output. It all boils down to this: >>>>>>>>> >>>>>>>>> The simulator merely watches its simulation of the following >>>>>>>>> instructions until it sees a function call to 377 from 503 the >>>>>>>>> second >>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>> >>>>>>>> >>>>>>>> I have told you many times that your test must be UNSOUND. You >>>>>>>> have >>>>>>>> never responded to this, so I've assumed you don't really know >>>>>>>> whether >>>>>>>> your test is sound or unsound (or probably, what that even means, >>>>>>>> although I've also explained that to you before). >>>>>>>> >>>>>>>> Now you are getting closer to actually coding the test (which you >>>>>>>> claimed to have "fully coded" two years ago), you are finally >>>>>>>> giving >>>>>>>> more details. >>>>>>>> >>>>>>>> So... what do you think. Is the following test a SOUND test for >>>>>>>> non-halting? >>>>>>>> >>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>> call to 377 from 503 a second time, with no conditional >>>>>>>> branch inbetween" >>>>>>>> >>>>>>>> Putting it more directly - if some calculation P(I) triggers the >>>>>>>> TEST >>>>>>>> (so it contains two calls from 377 from 503, with no conditional >>>>>>>> branch >>>>>>>> inbetween), does this genuinely imply that the calculation will >>>>>>>> never >>>>>>>> halt? >>>>>>>> >>>>>>>> Bear in mind that the two calls in question do not necessarily >>>>>>>> occur in >>>>>>>> the same "virtual address space", that is to say the two calls can >>>>>>>> [and >>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of >>>>>>>> emulation/. [Your trace notation obscures this simple fact, >>>>>>>> making >>>>>>>> everything appear to be in one single virtual process, when it's >>>>>>>> not.] >>>>>>>> >>>>>>>> What do you think? This seems to be your primary intuition that >>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY CORRECT? >>>>>>>> >>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>> definition - >>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>> >>>>>>>> Is TEST *SOUND* ? >>>>>>>> >>>>>>> >>>>>>> Noted: still no response to this basic question. >>>>>>> >>>>>>> Mike. >>>>>>> >>>>> <.. snip non-response to question ..> >>>>> >>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>> whether one specified implementation of [whatever] exhibits infinite >>>>> recursion! >>>>> >>>>> In case it was just a misreading, here is the question again. >>>>> >>>>> >>>>> So... what do you think. Is the following test a SOUND test for >>>>> non-halting? >>>>> >>>>> TEST: "monitor the simulation until there is a function >>>>> call to 377 from 503 a second time, with no conditional >>>>> branch in-between" >>>> >>>> It is much more generic than that. >>>> (1) Keep a global execution trace of every line of user code. >>>> >>>> (2) Whenever any instruction is executed see if it is a function call. >>>> >>>> (3) If it is a function call find the prior call to this same function >>>> from the current machine address (if any) searching backward through >>>> the >>>> global execution trace and counting conditional branch instructions. >>>> >>>> (4) If found and conditional-branch-count == zero terminate the input. >>>> >>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right now). >>> >>> OK, I always imagined the test would be more general than just >>> checking specifically for calls to 377 from 503. :) No problem on >>> that front. >>> >>> I'm thinking this is probably the basis of your initial intuition that >>> you could actually detect and handle the type of recursion in your >>> fledgeling (at that time) halt decider design. >>> >>> It is good that you've clarified the test, and yet it seems you're >>> reluctant to plainly say that you believe the test works! >> >> logical necessity speaks for itself it doesn't need me for a cheerleader. >> > > LOL. I knew you'd do something like that. > > OK, so you are saying that if your test detects the behaviour described, > then it's a "logical necessity" that the input being examined is > non-halting? Yes that is what I am saying. Can you find a counter-example? -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-26 01:38 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk> |
| In reply to | #25992 |
On 26/11/2020 00:51, olcott wrote:
> On 11/25/2020 6:33 PM, Mike Terry wrote:
>> On 25/11/2020 23:47, olcott wrote:
>>> On 11/25/2020 5:31 PM, Mike Terry wrote:
>>>> On 25/11/2020 21:55, olcott wrote:
>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote:
>>>>>> On 25/11/2020 17:21, olcott wrote:
>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote:
>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote:
>>>>>>>>> On 24/11/2020 04:18, olcott wrote:
>>>>>>>> <.. snip ..>
>>>>>>>>>>
>>>>>>>>>> People can eventually look at all of my code and the thousands of
>>>>>>>>>> lines
>>>>>>>>>> of code of the x86 emulator and they can look at the hundreds of
>>>>>>>>>> pages
>>>>>>>>>> out output. It all boils down to this:
>>>>>>>>>>
>>>>>>>>>> The simulator merely watches its simulation of the following
>>>>>>>>>> instructions until it sees a function call to 377 from 503 the
>>>>>>>>>> second
>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I have told you many times that your test must be UNSOUND. You
>>>>>>>>> have
>>>>>>>>> never responded to this, so I've assumed you don't really know
>>>>>>>>> whether
>>>>>>>>> your test is sound or unsound (or probably, what that even means,
>>>>>>>>> although I've also explained that to you before).
>>>>>>>>>
>>>>>>>>> Now you are getting closer to actually coding the test (which you
>>>>>>>>> claimed to have "fully coded" two years ago), you are finally
>>>>>>>>> giving
>>>>>>>>> more details.
>>>>>>>>>
>>>>>>>>> So... what do you think. Is the following test a SOUND test for
>>>>>>>>> non-halting?
>>>>>>>>>
>>>>>>>>> TEST: "monitor the simulation until there is a function
>>>>>>>>> call to 377 from 503 a second time, with no conditional
>>>>>>>>> branch inbetween"
>>>>>>>>>
>>>>>>>>> Putting it more directly - if some calculation P(I) triggers the
>>>>>>>>> TEST
>>>>>>>>> (so it contains two calls from 377 from 503, with no conditional
>>>>>>>>> branch
>>>>>>>>> inbetween), does this genuinely imply that the calculation will
>>>>>>>>> never
>>>>>>>>> halt?
>>>>>>>>>
>>>>>>>>> Bear in mind that the two calls in question do not necessarily
>>>>>>>>> occur in
>>>>>>>>> the same "virtual address space", that is to say the two calls can
>>>>>>>>> [and
>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of
>>>>>>>>> emulation/. [Your trace notation obscures this simple fact,
>>>>>>>>> making
>>>>>>>>> everything appear to be in one single virtual process, when it's
>>>>>>>>> not.]
>>>>>>>>>
>>>>>>>>> What do you think? This seems to be your primary intuition that
>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY
>>>>>>>>> CORRECT?
>>>>>>>>>
>>>>>>>>> Of course, you will say "All my intuitions are correct by
>>>>>>>>> definition -
>>>>>>>>> I'm never wrong" but that doesn't make it true! :)
>>>>>>>>>
>>>>>>>>> Is TEST *SOUND* ?
>>>>>>>>>
>>>>>>>>
>>>>>>>> Noted: still no response to this basic question.
>>>>>>>>
>>>>>>>> Mike.
>>>>>>>>
>>>>>> <.. snip non-response to question ..>
>>>>>>
>>>>>> I'm not sure if that non-response was deliberate. I didn't ask
>>>>>> whether one specified implementation of [whatever] exhibits infinite
>>>>>> recursion!
>>>>>>
>>>>>> In case it was just a misreading, here is the question again.
>>>>>>
>>>>>>
>>>>>> So... what do you think. Is the following test a SOUND test for
>>>>>> non-halting?
>>>>>>
>>>>>> TEST: "monitor the simulation until there is a function
>>>>>> call to 377 from 503 a second time, with no conditional
>>>>>> branch in-between"
>>>>>
>>>>> It is much more generic than that.
>>>>> (1) Keep a global execution trace of every line of user code.
>>>>>
>>>>> (2) Whenever any instruction is executed see if it is a function call.
>>>>>
>>>>> (3) If it is a function call find the prior call to this same function
>>>>> from the current machine address (if any) searching backward
>>>>> through the
>>>>> global execution trace and counting conditional branch instructions.
>>>>>
>>>>> (4) If found and conditional-branch-count == zero terminate the input.
>>>>>
>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right now).
>>>>
>>>> OK, I always imagined the test would be more general than just
>>>> checking specifically for calls to 377 from 503. :) No problem on
>>>> that front.
>>>>
>>>> I'm thinking this is probably the basis of your initial intuition that
>>>> you could actually detect and handle the type of recursion in your
>>>> fledgeling (at that time) halt decider design.
>>>>
>>>> It is good that you've clarified the test, and yet it seems you're
>>>> reluctant to plainly say that you believe the test works!
>>>
>>> logical necessity speaks for itself it doesn't need me for a
>>> cheerleader.
>>>
>>
>> LOL. I knew you'd do something like that.
>>
>> OK, so you are saying that if your test detects the behaviour
>> described, then it's a "logical necessity" that the input being
>> examined is non-halting?
>
> Yes that is what I am saying.
There - that wasn't so bad, was it? :)
>
> Can you find a counter-example?
Well, if it's a logical necessity I'm in for a hard time on that one...
But here's the point: logical necessity absolutely /does/ need a
cheerleader! Loads of things are "logically necessary" in that they
must logically be true, and yet they are not /obviously/ true. That's
why we have proofs.
This would be one of those scenarios, where even if your claim is
correct, it's not trivially obvious that it's correct, right?
Here is what we're saying:
TEST:
If a calculation P(I) has a trace of steps
(s0, s1, s2, s3, .....) and there are two steps s_i
and s_j, such that si and sj are both unconditional
branches from A to B, and none of the steps in-between
s_i and s_j are conditional branches, THEN calculation
P(I) never halts.
Well that's certainly not a "trivial restatement of word meanings" or
similar, and so is not seen to correct just on a casual glance.
So obviously where I'm going is : do you have a proof of this?
Now I know you're not one for proofs, and maybe during the course of
discussion such a proof will fall out (provided the underlying logic is
correct...)
So to start with, perhaps you can just give your thinking as to /why/
you believe it to be logically necessary? [You clearly didn't wake up
one day and think "hey, what about TEST - oh! it's a logical necessity,
that's handy - I can use it in my halt decider!". There was something
that led you to consider TEST, and having considered it, you decided for
whatever reason it was true...]
Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-25 20:14 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com> |
| In reply to | #26000 |
On 11/25/2020 7:38 PM, Mike Terry wrote: > On 26/11/2020 00:51, olcott wrote: >> On 11/25/2020 6:33 PM, Mike Terry wrote: >>> On 25/11/2020 23:47, olcott wrote: >>>> On 11/25/2020 5:31 PM, Mike Terry wrote: >>>>> On 25/11/2020 21:55, olcott wrote: >>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>>>> On 25/11/2020 17:21, olcott wrote: >>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>>>> <.. snip ..> >>>>>>>>>>> >>>>>>>>>>> People can eventually look at all of my code and the >>>>>>>>>>> thousands of >>>>>>>>>>> lines >>>>>>>>>>> of code of the x86 emulator and they can look at the hundreds of >>>>>>>>>>> pages >>>>>>>>>>> out output. It all boils down to this: >>>>>>>>>>> >>>>>>>>>>> The simulator merely watches its simulation of the following >>>>>>>>>>> instructions until it sees a function call to 377 from 503 the >>>>>>>>>>> second >>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> I have told you many times that your test must be UNSOUND. You >>>>>>>>>> have >>>>>>>>>> never responded to this, so I've assumed you don't really know >>>>>>>>>> whether >>>>>>>>>> your test is sound or unsound (or probably, what that even means, >>>>>>>>>> although I've also explained that to you before). >>>>>>>>>> >>>>>>>>>> Now you are getting closer to actually coding the test (which you >>>>>>>>>> claimed to have "fully coded" two years ago), you are finally >>>>>>>>>> giving >>>>>>>>>> more details. >>>>>>>>>> >>>>>>>>>> So... what do you think. Is the following test a SOUND test for >>>>>>>>>> non-halting? >>>>>>>>>> >>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>> conditional >>>>>>>>>> branch inbetween" >>>>>>>>>> >>>>>>>>>> Putting it more directly - if some calculation P(I) triggers the >>>>>>>>>> TEST >>>>>>>>>> (so it contains two calls from 377 from 503, with no conditional >>>>>>>>>> branch >>>>>>>>>> inbetween), does this genuinely imply that the calculation will >>>>>>>>>> never >>>>>>>>>> halt? >>>>>>>>>> >>>>>>>>>> Bear in mind that the two calls in question do not necessarily >>>>>>>>>> occur in >>>>>>>>>> the same "virtual address space", that is to say the two calls >>>>>>>>>> can >>>>>>>>>> [and >>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of >>>>>>>>>> emulation/. [Your trace notation obscures this simple fact, >>>>>>>>>> making >>>>>>>>>> everything appear to be in one single virtual process, when it's >>>>>>>>>> not.] >>>>>>>>>> >>>>>>>>>> What do you think? This seems to be your primary intuition that >>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY >>>>>>>>>> CORRECT? >>>>>>>>>> >>>>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>>>> definition - >>>>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>>>> >>>>>>>>>> Is TEST *SOUND* ? >>>>>>>>>> >>>>>>>>> >>>>>>>>> Noted: still no response to this basic question. >>>>>>>>> >>>>>>>>> Mike. >>>>>>>>> >>>>>>> <.. snip non-response to question ..> >>>>>>> >>>>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>>>> whether one specified implementation of [whatever] exhibits infinite >>>>>>> recursion! >>>>>>> >>>>>>> In case it was just a misreading, here is the question again. >>>>>>> >>>>>>> >>>>>>> So... what do you think. Is the following test a SOUND test for >>>>>>> non-halting? >>>>>>> >>>>>>> TEST: "monitor the simulation until there is a function >>>>>>> call to 377 from 503 a second time, with no >>>>>>> conditional >>>>>>> branch in-between" >>>>>> >>>>>> It is much more generic than that. >>>>>> (1) Keep a global execution trace of every line of user code. >>>>>> >>>>>> (2) Whenever any instruction is executed see if it is a function >>>>>> call. >>>>>> >>>>>> (3) If it is a function call find the prior call to this same >>>>>> function >>>>>> from the current machine address (if any) searching backward >>>>>> through the >>>>>> global execution trace and counting conditional branch instructions. >>>>>> >>>>>> (4) If found and conditional-branch-count == zero terminate the >>>>>> input. >>>>>> >>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right now). >>>>> >>>>> OK, I always imagined the test would be more general than just >>>>> checking specifically for calls to 377 from 503. :) No problem on >>>>> that front. >>>>> >>>>> I'm thinking this is probably the basis of your initial intuition that >>>>> you could actually detect and handle the type of recursion in your >>>>> fledgeling (at that time) halt decider design. >>>>> >>>>> It is good that you've clarified the test, and yet it seems you're >>>>> reluctant to plainly say that you believe the test works! >>>> >>>> logical necessity speaks for itself it doesn't need me for a >>>> cheerleader. >>>> >>> >>> LOL. I knew you'd do something like that. >>> >>> OK, so you are saying that if your test detects the behaviour >>> described, then it's a "logical necessity" that the input being >>> examined is non-halting? >> >> Yes that is what I am saying. > > There - that wasn't so bad, was it? :) > >> >> Can you find a counter-example? > > Well, if it's a logical necessity I'm in for a hard time on that one... > > But here's the point: logical necessity absolutely /does/ need a > cheerleader! Loads of things are "logically necessary" in that they > must logically be true, and yet they are not /obviously/ true. That's > why we have proofs. > > This would be one of those scenarios, where even if your claim is > correct, it's not trivially obvious that it's correct, right? > > Here is what we're saying: > > TEST: > If a calculation P(I) has a trace of steps > (s0, s1, s2, s3, .....) and there are two steps s_i > and s_j, such that si and sj are both unconditional > branches from A to B, and none of the steps in-between > s_i and s_j are conditional branches, THEN calculation > P(I) never halts. > > Well that's certainly not a "trivial restatement of word meanings" or > similar, and so is not seen to correct just on a casual glance. > > So obviously where I'm going is : do you have a proof of this? > > Now I know you're not one for proofs, and maybe during the course of > discussion such a proof will fall out (provided the underlying logic is > correct...) > > So to start with, perhaps you can just give your thinking as to /why/ > you believe it to be logically necessary? [You clearly didn't wake up > one day and think "hey, what about TEST - oh! it's a logical necessity, > that's handy - I can use it in my halt decider!". There was something > that led you to consider TEST, and having considered it, you decided for > whatever reason it was true...] > > > Mike. > Let's look at it a little simpler: HERE: // current location Instructions that cannot possibly exit a loop THERE: goto HERE; Can you see how this definitely loops? The next step is to make a list of every instruction that can exit a loop. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-26 04:27 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](impossibly incorrect) |
| Message-ID | <-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk> |
| In reply to | #26002 |
On 26/11/2020 02:14, olcott wrote: > On 11/25/2020 7:38 PM, Mike Terry wrote: >> On 26/11/2020 00:51, olcott wrote: >>> On 11/25/2020 6:33 PM, Mike Terry wrote: >>>> On 25/11/2020 23:47, olcott wrote: >>>>> On 11/25/2020 5:31 PM, Mike Terry wrote: >>>>>> On 25/11/2020 21:55, olcott wrote: >>>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>>>>> On 25/11/2020 17:21, olcott wrote: >>>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>>>>> <.. snip ..> >>>>>>>>>>>> >>>>>>>>>>>> People can eventually look at all of my code and the >>>>>>>>>>>> thousands of >>>>>>>>>>>> lines >>>>>>>>>>>> of code of the x86 emulator and they can look at the >>>>>>>>>>>> hundreds of >>>>>>>>>>>> pages >>>>>>>>>>>> out output. It all boils down to this: >>>>>>>>>>>> >>>>>>>>>>>> The simulator merely watches its simulation of the following >>>>>>>>>>>> instructions until it sees a function call to 377 from 503 the >>>>>>>>>>>> second >>>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> I have told you many times that your test must be UNSOUND. You >>>>>>>>>>> have >>>>>>>>>>> never responded to this, so I've assumed you don't really know >>>>>>>>>>> whether >>>>>>>>>>> your test is sound or unsound (or probably, what that even >>>>>>>>>>> means, >>>>>>>>>>> although I've also explained that to you before). >>>>>>>>>>> >>>>>>>>>>> Now you are getting closer to actually coding the test (which >>>>>>>>>>> you >>>>>>>>>>> claimed to have "fully coded" two years ago), you are finally >>>>>>>>>>> giving >>>>>>>>>>> more details. >>>>>>>>>>> >>>>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>>>> for >>>>>>>>>>> non-halting? >>>>>>>>>>> >>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>> conditional >>>>>>>>>>> branch inbetween" >>>>>>>>>>> >>>>>>>>>>> Putting it more directly - if some calculation P(I) triggers the >>>>>>>>>>> TEST >>>>>>>>>>> (so it contains two calls from 377 from 503, with no conditional >>>>>>>>>>> branch >>>>>>>>>>> inbetween), does this genuinely imply that the calculation will >>>>>>>>>>> never >>>>>>>>>>> halt? >>>>>>>>>>> >>>>>>>>>>> Bear in mind that the two calls in question do not necessarily >>>>>>>>>>> occur in >>>>>>>>>>> the same "virtual address space", that is to say the two >>>>>>>>>>> calls can >>>>>>>>>>> [and >>>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different levels of >>>>>>>>>>> emulation/. [Your trace notation obscures this simple fact, >>>>>>>>>>> making >>>>>>>>>>> everything appear to be in one single virtual process, when it's >>>>>>>>>>> not.] >>>>>>>>>>> >>>>>>>>>>> What do you think? This seems to be your primary intuition that >>>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY >>>>>>>>>>> CORRECT? >>>>>>>>>>> >>>>>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>>>>> definition - >>>>>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>>>>> >>>>>>>>>>> Is TEST *SOUND* ? >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> Noted: still no response to this basic question. >>>>>>>>>> >>>>>>>>>> Mike. >>>>>>>>>> >>>>>>>> <.. snip non-response to question ..> >>>>>>>> >>>>>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>>>>> whether one specified implementation of [whatever] exhibits >>>>>>>> infinite >>>>>>>> recursion! >>>>>>>> >>>>>>>> In case it was just a misreading, here is the question again. >>>>>>>> >>>>>>>> >>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>> for >>>>>>>> non-halting? >>>>>>>> >>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>> call to 377 from 503 a second time, with no >>>>>>>> conditional >>>>>>>> branch in-between" >>>>>>> >>>>>>> It is much more generic than that. >>>>>>> (1) Keep a global execution trace of every line of user code. >>>>>>> >>>>>>> (2) Whenever any instruction is executed see if it is a function >>>>>>> call. >>>>>>> >>>>>>> (3) If it is a function call find the prior call to this same >>>>>>> function >>>>>>> from the current machine address (if any) searching backward >>>>>>> through the >>>>>>> global execution trace and counting conditional branch instructions. >>>>>>> >>>>>>> (4) If found and conditional-branch-count == zero terminate the >>>>>>> input. >>>>>>> >>>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right now). >>>>>> >>>>>> OK, I always imagined the test would be more general than just >>>>>> checking specifically for calls to 377 from 503. :) No problem on >>>>>> that front. >>>>>> >>>>>> I'm thinking this is probably the basis of your initial intuition >>>>>> that >>>>>> you could actually detect and handle the type of recursion in your >>>>>> fledgeling (at that time) halt decider design. >>>>>> >>>>>> It is good that you've clarified the test, and yet it seems you're >>>>>> reluctant to plainly say that you believe the test works! >>>>> >>>>> logical necessity speaks for itself it doesn't need me for a >>>>> cheerleader. >>>>> >>>> >>>> LOL. I knew you'd do something like that. >>>> >>>> OK, so you are saying that if your test detects the behaviour >>>> described, then it's a "logical necessity" that the input being >>>> examined is non-halting? >>> >>> Yes that is what I am saying. >> >> There - that wasn't so bad, was it? :) >> >>> >>> Can you find a counter-example? >> >> Well, if it's a logical necessity I'm in for a hard time on that one... >> >> But here's the point: logical necessity absolutely /does/ need a >> cheerleader! Loads of things are "logically necessary" in that they >> must logically be true, and yet they are not /obviously/ true. That's >> why we have proofs. >> >> This would be one of those scenarios, where even if your claim is >> correct, it's not trivially obvious that it's correct, right? >> >> Here is what we're saying: >> >> TEST: >> If a calculation P(I) has a trace of steps >> (s0, s1, s2, s3, .....) and there are two steps s_i >> and s_j, such that si and sj are both unconditional >> branches from A to B, and none of the steps in-between >> s_i and s_j are conditional branches, THEN calculation >> P(I) never halts. >> >> Well that's certainly not a "trivial restatement of word meanings" or >> similar, and so is not seen to correct just on a casual glance. >> >> So obviously where I'm going is : do you have a proof of this? >> >> Now I know you're not one for proofs, and maybe during the course of >> discussion such a proof will fall out (provided the underlying logic >> is correct...) >> >> So to start with, perhaps you can just give your thinking as to /why/ >> you believe it to be logically necessary? [You clearly didn't wake up >> one day and think "hey, what about TEST - oh! it's a logical >> necessity, that's handy - I can use it in my halt decider!". There >> was something that led you to consider TEST, and having considered it, >> you decided for whatever reason it was true...] >> >> >> Mike. >> > > Let's look at it a little simpler: > HERE: // current location > Instructions that cannot possibly exit a loop > THERE: goto HERE; > > Can you see how this definitely loops? I can - and if this was relevant there would be a straight forward proof that such code loops. But this isn't like the scenario you are dealing with AT ALL! What you are showing here is a kind of "in-process" loop detection. What you need is some kind of recursive EMULATION detection. (Emulation works differently in this respect.) I'm pretty sure I explained the difference in a post a couple of weeks ago but you never responded. > > The next step is to make a list of every instruction that can exit a loop. Yes, I see where you're going with that, but it's not going to work for the situation you need to cover... But you are genuinely trying to answer my question, which I appreciate. Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-25 22:39 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) |
| Message-ID | <p7SdnUWV3YT3rCLCnZ2dnUU7-KnNnZ2d@giganews.com> |
| In reply to | #26018 |
On 11/25/2020 10:27 PM, Mike Terry wrote: > On 26/11/2020 02:14, olcott wrote: >> On 11/25/2020 7:38 PM, Mike Terry wrote: >>> On 26/11/2020 00:51, olcott wrote: >>>> On 11/25/2020 6:33 PM, Mike Terry wrote: >>>>> On 25/11/2020 23:47, olcott wrote: >>>>>> On 11/25/2020 5:31 PM, Mike Terry wrote: >>>>>>> On 25/11/2020 21:55, olcott wrote: >>>>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>>>>>> On 25/11/2020 17:21, olcott wrote: >>>>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>>>>>> <.. snip ..> >>>>>>>>>>>>> >>>>>>>>>>>>> People can eventually look at all of my code and the >>>>>>>>>>>>> thousands of >>>>>>>>>>>>> lines >>>>>>>>>>>>> of code of the x86 emulator and they can look at the >>>>>>>>>>>>> hundreds of >>>>>>>>>>>>> pages >>>>>>>>>>>>> out output. It all boils down to this: >>>>>>>>>>>>> >>>>>>>>>>>>> The simulator merely watches its simulation of the following >>>>>>>>>>>>> instructions until it sees a function call to 377 from 503 the >>>>>>>>>>>>> second >>>>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> I have told you many times that your test must be UNSOUND. You >>>>>>>>>>>> have >>>>>>>>>>>> never responded to this, so I've assumed you don't really know >>>>>>>>>>>> whether >>>>>>>>>>>> your test is sound or unsound (or probably, what that even >>>>>>>>>>>> means, >>>>>>>>>>>> although I've also explained that to you before). >>>>>>>>>>>> >>>>>>>>>>>> Now you are getting closer to actually coding the test (which >>>>>>>>>>>> you >>>>>>>>>>>> claimed to have "fully coded" two years ago), you are finally >>>>>>>>>>>> giving >>>>>>>>>>>> more details. >>>>>>>>>>>> >>>>>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>>>>> for >>>>>>>>>>>> non-halting? >>>>>>>>>>>> >>>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>>> conditional >>>>>>>>>>>> branch inbetween" >>>>>>>>>>>> >>>>>>>>>>>> Putting it more directly - if some calculation P(I) triggers >>>>>>>>>>>> the >>>>>>>>>>>> TEST >>>>>>>>>>>> (so it contains two calls from 377 from 503, with no >>>>>>>>>>>> conditional >>>>>>>>>>>> branch >>>>>>>>>>>> inbetween), does this genuinely imply that the calculation will >>>>>>>>>>>> never >>>>>>>>>>>> halt? >>>>>>>>>>>> >>>>>>>>>>>> Bear in mind that the two calls in question do not necessarily >>>>>>>>>>>> occur in >>>>>>>>>>>> the same "virtual address space", that is to say the two >>>>>>>>>>>> calls can >>>>>>>>>>>> [and >>>>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different >>>>>>>>>>>> levels of >>>>>>>>>>>> emulation/. [Your trace notation obscures this simple fact, >>>>>>>>>>>> making >>>>>>>>>>>> everything appear to be in one single virtual process, when >>>>>>>>>>>> it's >>>>>>>>>>>> not.] >>>>>>>>>>>> >>>>>>>>>>>> What do you think? This seems to be your primary intuition >>>>>>>>>>>> that >>>>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY >>>>>>>>>>>> CORRECT? >>>>>>>>>>>> >>>>>>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>>>>>> definition - >>>>>>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>>>>>> >>>>>>>>>>>> Is TEST *SOUND* ? >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> Noted: still no response to this basic question. >>>>>>>>>>> >>>>>>>>>>> Mike. >>>>>>>>>>> >>>>>>>>> <.. snip non-response to question ..> >>>>>>>>> >>>>>>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>>>>>> whether one specified implementation of [whatever] exhibits >>>>>>>>> infinite >>>>>>>>> recursion! >>>>>>>>> >>>>>>>>> In case it was just a misreading, here is the question again. >>>>>>>>> >>>>>>>>> >>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>> for >>>>>>>>> non-halting? >>>>>>>>> >>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>> conditional >>>>>>>>> branch in-between" >>>>>>>> >>>>>>>> It is much more generic than that. >>>>>>>> (1) Keep a global execution trace of every line of user code. >>>>>>>> >>>>>>>> (2) Whenever any instruction is executed see if it is a function >>>>>>>> call. >>>>>>>> >>>>>>>> (3) If it is a function call find the prior call to this same >>>>>>>> function >>>>>>>> from the current machine address (if any) searching backward >>>>>>>> through the >>>>>>>> global execution trace and counting conditional branch >>>>>>>> instructions. >>>>>>>> >>>>>>>> (4) If found and conditional-branch-count == zero terminate the >>>>>>>> input. >>>>>>>> >>>>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right now). >>>>>>> >>>>>>> OK, I always imagined the test would be more general than just >>>>>>> checking specifically for calls to 377 from 503. :) No problem on >>>>>>> that front. >>>>>>> >>>>>>> I'm thinking this is probably the basis of your initial intuition >>>>>>> that >>>>>>> you could actually detect and handle the type of recursion in your >>>>>>> fledgeling (at that time) halt decider design. >>>>>>> >>>>>>> It is good that you've clarified the test, and yet it seems you're >>>>>>> reluctant to plainly say that you believe the test works! >>>>>> >>>>>> logical necessity speaks for itself it doesn't need me for a >>>>>> cheerleader. >>>>>> >>>>> >>>>> LOL. I knew you'd do something like that. >>>>> >>>>> OK, so you are saying that if your test detects the behaviour >>>>> described, then it's a "logical necessity" that the input being >>>>> examined is non-halting? >>>> >>>> Yes that is what I am saying. >>> >>> There - that wasn't so bad, was it? :) >>> >>>> >>>> Can you find a counter-example? >>> >>> Well, if it's a logical necessity I'm in for a hard time on that one... >>> >>> But here's the point: logical necessity absolutely /does/ need a >>> cheerleader! Loads of things are "logically necessary" in that they >>> must logically be true, and yet they are not /obviously/ true. That's >>> why we have proofs. >>> >>> This would be one of those scenarios, where even if your claim is >>> correct, it's not trivially obvious that it's correct, right? >>> >>> Here is what we're saying: >>> >>> TEST: >>> If a calculation P(I) has a trace of steps >>> (s0, s1, s2, s3, .....) and there are two steps s_i >>> and s_j, such that si and sj are both unconditional >>> branches from A to B, and none of the steps in-between >>> s_i and s_j are conditional branches, THEN calculation >>> P(I) never halts. >>> >>> Well that's certainly not a "trivial restatement of word meanings" or >>> similar, and so is not seen to correct just on a casual glance. >>> >>> So obviously where I'm going is : do you have a proof of this? >>> >>> Now I know you're not one for proofs, and maybe during the course of >>> discussion such a proof will fall out (provided the underlying logic >>> is correct...) >>> >>> So to start with, perhaps you can just give your thinking as to /why/ >>> you believe it to be logically necessary? [You clearly didn't wake up >>> one day and think "hey, what about TEST - oh! it's a logical >>> necessity, that's handy - I can use it in my halt decider!". There >>> was something that led you to consider TEST, and having considered it, >>> you decided for whatever reason it was true...] >>> >>> >>> Mike. >>> >> >> Let's look at it a little simpler: >> HERE: // current location >> Instructions that cannot possibly exit a loop >> THERE: goto HERE; >> >> Can you see how this definitely loops? > > I can - and if this was relevant there would be a straight forward proof > that such code loops. > > But this isn't like the scenario you are dealing with AT ALL! What you > are showing here is a kind of "in-process" loop detection. What you > need is some kind of recursive EMULATION detection. (Emulation works > differently in this respect.) > > I'm pretty sure I explained the difference in a post a couple of weeks > ago but you never responded. We are trying to determine whether or not a specific sequence of x86 machine code bytes specify an infinite loop as if this machine code was a mathematical formalism. The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY? > >> >> The next step is to make a list of every instruction that can exit a >> loop. > > Yes, I see where you're going with that, but it's not going to work for > the situation you need to cover... > > But you are genuinely trying to answer my question, which I appreciate. > > Mike. > -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-26 15:48 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) |
| Message-ID | <G9ednQR63dvHUyLCnZ2dnUU78QnNnZ2d@brightview.co.uk> |
| In reply to | #26020 |
On 26/11/2020 04:39, olcott wrote: > On 11/25/2020 10:27 PM, Mike Terry wrote: >> On 26/11/2020 02:14, olcott wrote: >>> On 11/25/2020 7:38 PM, Mike Terry wrote: >>>> On 26/11/2020 00:51, olcott wrote: >>>>> On 11/25/2020 6:33 PM, Mike Terry wrote: >>>>>> On 25/11/2020 23:47, olcott wrote: >>>>>>> On 11/25/2020 5:31 PM, Mike Terry wrote: >>>>>>>> On 25/11/2020 21:55, olcott wrote: >>>>>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>>>>>>> On 25/11/2020 17:21, olcott wrote: >>>>>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>>>>>>> <.. snip ..> >>>>>>>>>>>>>> >>>>>>>>>>>>>> People can eventually look at all of my code and the >>>>>>>>>>>>>> thousands of >>>>>>>>>>>>>> lines >>>>>>>>>>>>>> of code of the x86 emulator and they can look at the >>>>>>>>>>>>>> hundreds of >>>>>>>>>>>>>> pages >>>>>>>>>>>>>> out output. It all boils down to this: >>>>>>>>>>>>>> >>>>>>>>>>>>>> The simulator merely watches its simulation of the following >>>>>>>>>>>>>> instructions until it sees a function call to 377 from 503 >>>>>>>>>>>>>> the >>>>>>>>>>>>>> second >>>>>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> I have told you many times that your test must be UNSOUND. >>>>>>>>>>>>> You >>>>>>>>>>>>> have >>>>>>>>>>>>> never responded to this, so I've assumed you don't really know >>>>>>>>>>>>> whether >>>>>>>>>>>>> your test is sound or unsound (or probably, what that even >>>>>>>>>>>>> means, >>>>>>>>>>>>> although I've also explained that to you before). >>>>>>>>>>>>> >>>>>>>>>>>>> Now you are getting closer to actually coding the test (which >>>>>>>>>>>>> you >>>>>>>>>>>>> claimed to have "fully coded" two years ago), you are finally >>>>>>>>>>>>> giving >>>>>>>>>>>>> more details. >>>>>>>>>>>>> >>>>>>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>>>>>> for >>>>>>>>>>>>> non-halting? >>>>>>>>>>>>> >>>>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>>>> conditional >>>>>>>>>>>>> branch inbetween" >>>>>>>>>>>>> >>>>>>>>>>>>> Putting it more directly - if some calculation P(I) >>>>>>>>>>>>> triggers the >>>>>>>>>>>>> TEST >>>>>>>>>>>>> (so it contains two calls from 377 from 503, with no >>>>>>>>>>>>> conditional >>>>>>>>>>>>> branch >>>>>>>>>>>>> inbetween), does this genuinely imply that the calculation >>>>>>>>>>>>> will >>>>>>>>>>>>> never >>>>>>>>>>>>> halt? >>>>>>>>>>>>> >>>>>>>>>>>>> Bear in mind that the two calls in question do not necessarily >>>>>>>>>>>>> occur in >>>>>>>>>>>>> the same "virtual address space", that is to say the two >>>>>>>>>>>>> calls can >>>>>>>>>>>>> [and >>>>>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different >>>>>>>>>>>>> levels of >>>>>>>>>>>>> emulation/. [Your trace notation obscures this simple fact, >>>>>>>>>>>>> making >>>>>>>>>>>>> everything appear to be in one single virtual process, when >>>>>>>>>>>>> it's >>>>>>>>>>>>> not.] >>>>>>>>>>>>> >>>>>>>>>>>>> What do you think? This seems to be your primary intuition >>>>>>>>>>>>> that >>>>>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY >>>>>>>>>>>>> CORRECT? >>>>>>>>>>>>> >>>>>>>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>>>>>>> definition - >>>>>>>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>>>>>>> >>>>>>>>>>>>> Is TEST *SOUND* ? >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> Noted: still no response to this basic question. >>>>>>>>>>>> >>>>>>>>>>>> Mike. >>>>>>>>>>>> >>>>>>>>>> <.. snip non-response to question ..> >>>>>>>>>> >>>>>>>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>>>>>>> whether one specified implementation of [whatever] exhibits >>>>>>>>>> infinite >>>>>>>>>> recursion! >>>>>>>>>> >>>>>>>>>> In case it was just a misreading, here is the question again. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>>> for >>>>>>>>>> non-halting? >>>>>>>>>> >>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>> conditional >>>>>>>>>> branch in-between" >>>>>>>>> >>>>>>>>> It is much more generic than that. >>>>>>>>> (1) Keep a global execution trace of every line of user code. >>>>>>>>> >>>>>>>>> (2) Whenever any instruction is executed see if it is a function >>>>>>>>> call. >>>>>>>>> >>>>>>>>> (3) If it is a function call find the prior call to this same >>>>>>>>> function >>>>>>>>> from the current machine address (if any) searching backward >>>>>>>>> through the >>>>>>>>> global execution trace and counting conditional branch >>>>>>>>> instructions. >>>>>>>>> >>>>>>>>> (4) If found and conditional-branch-count == zero terminate the >>>>>>>>> input. >>>>>>>>> >>>>>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right >>>>>>>>> now). >>>>>>>> >>>>>>>> OK, I always imagined the test would be more general than just >>>>>>>> checking specifically for calls to 377 from 503. :) No problem on >>>>>>>> that front. >>>>>>>> >>>>>>>> I'm thinking this is probably the basis of your initial intuition >>>>>>>> that >>>>>>>> you could actually detect and handle the type of recursion in your >>>>>>>> fledgeling (at that time) halt decider design. >>>>>>>> >>>>>>>> It is good that you've clarified the test, and yet it seems you're >>>>>>>> reluctant to plainly say that you believe the test works! >>>>>>> >>>>>>> logical necessity speaks for itself it doesn't need me for a >>>>>>> cheerleader. >>>>>>> >>>>>> >>>>>> LOL. I knew you'd do something like that. >>>>>> >>>>>> OK, so you are saying that if your test detects the behaviour >>>>>> described, then it's a "logical necessity" that the input being >>>>>> examined is non-halting? >>>>> >>>>> Yes that is what I am saying. >>>> >>>> There - that wasn't so bad, was it? :) >>>> >>>>> >>>>> Can you find a counter-example? >>>> >>>> Well, if it's a logical necessity I'm in for a hard time on that one... >>>> >>>> But here's the point: logical necessity absolutely /does/ need a >>>> cheerleader! Loads of things are "logically necessary" in that they >>>> must logically be true, and yet they are not /obviously/ true. That's >>>> why we have proofs. >>>> >>>> This would be one of those scenarios, where even if your claim is >>>> correct, it's not trivially obvious that it's correct, right? >>>> >>>> Here is what we're saying: >>>> >>>> TEST: >>>> If a calculation P(I) has a trace of steps >>>> (s0, s1, s2, s3, .....) and there are two steps s_i >>>> and s_j, such that si and sj are both unconditional >>>> branches from A to B, and none of the steps in-between >>>> s_i and s_j are conditional branches, THEN calculation >>>> P(I) never halts. >>>> >>>> Well that's certainly not a "trivial restatement of word meanings" or >>>> similar, and so is not seen to correct just on a casual glance. >>>> >>>> So obviously where I'm going is : do you have a proof of this? >>>> >>>> Now I know you're not one for proofs, and maybe during the course of >>>> discussion such a proof will fall out (provided the underlying logic >>>> is correct...) >>>> >>>> So to start with, perhaps you can just give your thinking as to /why/ >>>> you believe it to be logically necessary? [You clearly didn't wake up >>>> one day and think "hey, what about TEST - oh! it's a logical >>>> necessity, that's handy - I can use it in my halt decider!". There >>>> was something that led you to consider TEST, and having considered it, >>>> you decided for whatever reason it was true...] >>>> >>>> >>>> Mike. >>>> >>> >>> Let's look at it a little simpler: >>> HERE: // current location >>> Instructions that cannot possibly exit a loop >>> THERE: goto HERE; >>> >>> Can you see how this definitely loops? >> >> I can - and if this was relevant there would be a straight forward >> proof that such code loops. >> >> But this isn't like the scenario you are dealing with AT ALL! What >> you are showing here is a kind of "in-process" loop detection. What >> you need is some kind of recursive EMULATION detection. (Emulation >> works differently in this respect.) >> >> I'm pretty sure I explained the difference in a post a couple of weeks >> ago but you never responded. > > We are trying to determine whether or not a specific sequence of x86 > machine code bytes specify an infinite loop as if this machine code was > a mathematical formalism. > > The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY? > Well, I understand that the code bytes that you presented, if executed by a processor within one single logical thread of execution, would never terminate - there is an obvious loop. But that's ignoring the issue of RECURSION, where behaviour is not so simple. So what's the next step? (So far what you've said is no justification for the RECUSION scenario, which is what you TEST is concerned with.) Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-26 10:07 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) |
| Message-ID | <PfmdnUdnnqhYTyLCnZ2dnUU7-c3NnZ2d@giganews.com> |
| In reply to | #26027 |
On 11/26/2020 9:48 AM, Mike Terry wrote: > On 26/11/2020 04:39, olcott wrote: >> On 11/25/2020 10:27 PM, Mike Terry wrote: >>> On 26/11/2020 02:14, olcott wrote: >>>> On 11/25/2020 7:38 PM, Mike Terry wrote: >>>>> On 26/11/2020 00:51, olcott wrote: >>>>>> On 11/25/2020 6:33 PM, Mike Terry wrote: >>>>>>> On 25/11/2020 23:47, olcott wrote: >>>>>>>> On 11/25/2020 5:31 PM, Mike Terry wrote: >>>>>>>>> On 25/11/2020 21:55, olcott wrote: >>>>>>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>>>>>>>> On 25/11/2020 17:21, olcott wrote: >>>>>>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>>>>>>>> <.. snip ..> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> People can eventually look at all of my code and the >>>>>>>>>>>>>>> thousands of >>>>>>>>>>>>>>> lines >>>>>>>>>>>>>>> of code of the x86 emulator and they can look at the >>>>>>>>>>>>>>> hundreds of >>>>>>>>>>>>>>> pages >>>>>>>>>>>>>>> out output. It all boils down to this: >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> The simulator merely watches its simulation of the following >>>>>>>>>>>>>>> instructions until it sees a function call to 377 from 503 >>>>>>>>>>>>>>> the >>>>>>>>>>>>>>> second >>>>>>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> I have told you many times that your test must be UNSOUND. >>>>>>>>>>>>>> You >>>>>>>>>>>>>> have >>>>>>>>>>>>>> never responded to this, so I've assumed you don't really >>>>>>>>>>>>>> know >>>>>>>>>>>>>> whether >>>>>>>>>>>>>> your test is sound or unsound (or probably, what that even >>>>>>>>>>>>>> means, >>>>>>>>>>>>>> although I've also explained that to you before). >>>>>>>>>>>>>> >>>>>>>>>>>>>> Now you are getting closer to actually coding the test (which >>>>>>>>>>>>>> you >>>>>>>>>>>>>> claimed to have "fully coded" two years ago), you are finally >>>>>>>>>>>>>> giving >>>>>>>>>>>>>> more details. >>>>>>>>>>>>>> >>>>>>>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>>>>>>> for >>>>>>>>>>>>>> non-halting? >>>>>>>>>>>>>> >>>>>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>>>>> conditional >>>>>>>>>>>>>> branch inbetween" >>>>>>>>>>>>>> >>>>>>>>>>>>>> Putting it more directly - if some calculation P(I) >>>>>>>>>>>>>> triggers the >>>>>>>>>>>>>> TEST >>>>>>>>>>>>>> (so it contains two calls from 377 from 503, with no >>>>>>>>>>>>>> conditional >>>>>>>>>>>>>> branch >>>>>>>>>>>>>> inbetween), does this genuinely imply that the calculation >>>>>>>>>>>>>> will >>>>>>>>>>>>>> never >>>>>>>>>>>>>> halt? >>>>>>>>>>>>>> >>>>>>>>>>>>>> Bear in mind that the two calls in question do not >>>>>>>>>>>>>> necessarily >>>>>>>>>>>>>> occur in >>>>>>>>>>>>>> the same "virtual address space", that is to say the two >>>>>>>>>>>>>> calls can >>>>>>>>>>>>>> [and >>>>>>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different >>>>>>>>>>>>>> levels of >>>>>>>>>>>>>> emulation/. [Your trace notation obscures this simple fact, >>>>>>>>>>>>>> making >>>>>>>>>>>>>> everything appear to be in one single virtual process, when >>>>>>>>>>>>>> it's >>>>>>>>>>>>>> not.] >>>>>>>>>>>>>> >>>>>>>>>>>>>> What do you think? This seems to be your primary intuition >>>>>>>>>>>>>> that >>>>>>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY >>>>>>>>>>>>>> CORRECT? >>>>>>>>>>>>>> >>>>>>>>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>>>>>>>> definition - >>>>>>>>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>>>>>>>> >>>>>>>>>>>>>> Is TEST *SOUND* ? >>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> Noted: still no response to this basic question. >>>>>>>>>>>>> >>>>>>>>>>>>> Mike. >>>>>>>>>>>>> >>>>>>>>>>> <.. snip non-response to question ..> >>>>>>>>>>> >>>>>>>>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>>>>>>>> whether one specified implementation of [whatever] exhibits >>>>>>>>>>> infinite >>>>>>>>>>> recursion! >>>>>>>>>>> >>>>>>>>>>> In case it was just a misreading, here is the question again. >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> So... what do you think. Is the following test a SOUND test >>>>>>>>>>> for >>>>>>>>>>> non-halting? >>>>>>>>>>> >>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>> conditional >>>>>>>>>>> branch in-between" >>>>>>>>>> >>>>>>>>>> It is much more generic than that. >>>>>>>>>> (1) Keep a global execution trace of every line of user code. >>>>>>>>>> >>>>>>>>>> (2) Whenever any instruction is executed see if it is a function >>>>>>>>>> call. >>>>>>>>>> >>>>>>>>>> (3) If it is a function call find the prior call to this same >>>>>>>>>> function >>>>>>>>>> from the current machine address (if any) searching backward >>>>>>>>>> through the >>>>>>>>>> global execution trace and counting conditional branch >>>>>>>>>> instructions. >>>>>>>>>> >>>>>>>>>> (4) If found and conditional-branch-count == zero terminate the >>>>>>>>>> input. >>>>>>>>>> >>>>>>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right >>>>>>>>>> now). >>>>>>>>> >>>>>>>>> OK, I always imagined the test would be more general than just >>>>>>>>> checking specifically for calls to 377 from 503. :) No >>>>>>>>> problem on >>>>>>>>> that front. >>>>>>>>> >>>>>>>>> I'm thinking this is probably the basis of your initial intuition >>>>>>>>> that >>>>>>>>> you could actually detect and handle the type of recursion in your >>>>>>>>> fledgeling (at that time) halt decider design. >>>>>>>>> >>>>>>>>> It is good that you've clarified the test, and yet it seems you're >>>>>>>>> reluctant to plainly say that you believe the test works! >>>>>>>> >>>>>>>> logical necessity speaks for itself it doesn't need me for a >>>>>>>> cheerleader. >>>>>>>> >>>>>>> >>>>>>> LOL. I knew you'd do something like that. >>>>>>> >>>>>>> OK, so you are saying that if your test detects the behaviour >>>>>>> described, then it's a "logical necessity" that the input being >>>>>>> examined is non-halting? >>>>>> >>>>>> Yes that is what I am saying. >>>>> >>>>> There - that wasn't so bad, was it? :) >>>>> >>>>>> >>>>>> Can you find a counter-example? >>>>> >>>>> Well, if it's a logical necessity I'm in for a hard time on that >>>>> one... >>>>> >>>>> But here's the point: logical necessity absolutely /does/ need a >>>>> cheerleader! Loads of things are "logically necessary" in that they >>>>> must logically be true, and yet they are not /obviously/ true. That's >>>>> why we have proofs. >>>>> >>>>> This would be one of those scenarios, where even if your claim is >>>>> correct, it's not trivially obvious that it's correct, right? >>>>> >>>>> Here is what we're saying: >>>>> >>>>> TEST: >>>>> If a calculation P(I) has a trace of steps >>>>> (s0, s1, s2, s3, .....) and there are two steps s_i >>>>> and s_j, such that si and sj are both unconditional >>>>> branches from A to B, and none of the steps in-between >>>>> s_i and s_j are conditional branches, THEN calculation >>>>> P(I) never halts. >>>>> >>>>> Well that's certainly not a "trivial restatement of word meanings" or >>>>> similar, and so is not seen to correct just on a casual glance. >>>>> >>>>> So obviously where I'm going is : do you have a proof of this? >>>>> >>>>> Now I know you're not one for proofs, and maybe during the course of >>>>> discussion such a proof will fall out (provided the underlying logic >>>>> is correct...) >>>>> >>>>> So to start with, perhaps you can just give your thinking as to /why/ >>>>> you believe it to be logically necessary? [You clearly didn't wake up >>>>> one day and think "hey, what about TEST - oh! it's a logical >>>>> necessity, that's handy - I can use it in my halt decider!". There >>>>> was something that led you to consider TEST, and having considered it, >>>>> you decided for whatever reason it was true...] >>>>> >>>>> >>>>> Mike. >>>>> >>>> >>>> Let's look at it a little simpler: >>>> HERE: // current location >>>> Instructions that cannot possibly exit a loop >>>> THERE: goto HERE; >>>> >>>> Can you see how this definitely loops? >>> >>> I can - and if this was relevant there would be a straight forward >>> proof that such code loops. >>> >>> But this isn't like the scenario you are dealing with AT ALL! What >>> you are showing here is a kind of "in-process" loop detection. What >>> you need is some kind of recursive EMULATION detection. (Emulation >>> works differently in this respect.) >>> >>> I'm pretty sure I explained the difference in a post a couple of weeks >>> ago but you never responded. >> >> We are trying to determine whether or not a specific sequence of x86 >> machine code bytes specify an infinite loop as if this machine code was >> a mathematical formalism. >> >> The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY? >> > > Well, I understand that the code bytes that you presented, if executed > by a processor within one single logical thread of execution, would > never terminate - there is an obvious loop. > > But that's ignoring the issue of RECURSION, where behaviour is not so > simple. So what's the next step? (So far what you've said is no > justification for the RECUSION scenario, which is what you TEST is > concerned with.) > > Mike. > The sequences of instructions from HERE to THERE and HERE to HERE are from actual execution traces. The x86 emulator screens out all dead code and only shows us the code that is actually reached. -HERE: // current location - Instructions that cannot possibly exit a loop -THERE: goto HERE; To form a mathematical proof on the basis of the x86 language being construed as a formal language we only have to derive the complete list of every instruction that can possibly exit the above loop and if there are none of these between the labels HERE and THERE then we know that the loop is infinite. The case for infinite recursion is similar. -HERE: Call Function At Address X - Instructions that cannot possibly exit recursion -HERE: Call Function At Address X If there are no instructions that can possibly exit recursion between invocations of the same function from the same machine address, then recursion is infinite. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-26 16:30 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) |
| Message-ID | <U8ednVm41KijRSLCnZ2dnUU78c_NnZ2d@brightview.co.uk> |
| In reply to | #26030 |
On 26/11/2020 16:07, olcott wrote: > On 11/26/2020 9:48 AM, Mike Terry wrote: >> On 26/11/2020 04:39, olcott wrote: >>> On 11/25/2020 10:27 PM, Mike Terry wrote: >>>> On 26/11/2020 02:14, olcott wrote: >>>>> On 11/25/2020 7:38 PM, Mike Terry wrote: >>>>>> On 26/11/2020 00:51, olcott wrote: >>>>>>> On 11/25/2020 6:33 PM, Mike Terry wrote: >>>>>>>> On 25/11/2020 23:47, olcott wrote: >>>>>>>>> On 11/25/2020 5:31 PM, Mike Terry wrote: >>>>>>>>>> On 25/11/2020 21:55, olcott wrote: >>>>>>>>>>> On 11/25/2020 3:25 PM, Mike Terry wrote: >>>>>>>>>>>> On 25/11/2020 17:21, olcott wrote: >>>>>>>>>>>>> On 11/25/2020 10:45 AM, Mike Terry wrote: >>>>>>>>>>>>>> On 24/11/2020 15:41, Mike Terry wrote: >>>>>>>>>>>>>>> On 24/11/2020 04:18, olcott wrote: >>>>>>>>>>>>>> <.. snip ..> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> People can eventually look at all of my code and the >>>>>>>>>>>>>>>> thousands of >>>>>>>>>>>>>>>> lines >>>>>>>>>>>>>>>> of code of the x86 emulator and they can look at the >>>>>>>>>>>>>>>> hundreds of >>>>>>>>>>>>>>>> pages >>>>>>>>>>>>>>>> out output. It all boils down to this: >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> The simulator merely watches its simulation of the >>>>>>>>>>>>>>>> following >>>>>>>>>>>>>>>> instructions until it sees a function call to 377 from 503 >>>>>>>>>>>>>>>> the >>>>>>>>>>>>>>>> second >>>>>>>>>>>>>>>> time with no JCC (Jump-Condition_Code) in-between. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> I have told you many times that your test must be UNSOUND. >>>>>>>>>>>>>>> You >>>>>>>>>>>>>>> have >>>>>>>>>>>>>>> never responded to this, so I've assumed you don't really >>>>>>>>>>>>>>> know >>>>>>>>>>>>>>> whether >>>>>>>>>>>>>>> your test is sound or unsound (or probably, what that even >>>>>>>>>>>>>>> means, >>>>>>>>>>>>>>> although I've also explained that to you before). >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Now you are getting closer to actually coding the test >>>>>>>>>>>>>>> (which >>>>>>>>>>>>>>> you >>>>>>>>>>>>>>> claimed to have "fully coded" two years ago), you are >>>>>>>>>>>>>>> finally >>>>>>>>>>>>>>> giving >>>>>>>>>>>>>>> more details. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> So... what do you think. Is the following test a SOUND >>>>>>>>>>>>>>> test >>>>>>>>>>>>>>> for >>>>>>>>>>>>>>> non-halting? >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>>>>>> conditional >>>>>>>>>>>>>>> branch inbetween" >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Putting it more directly - if some calculation P(I) >>>>>>>>>>>>>>> triggers the >>>>>>>>>>>>>>> TEST >>>>>>>>>>>>>>> (so it contains two calls from 377 from 503, with no >>>>>>>>>>>>>>> conditional >>>>>>>>>>>>>>> branch >>>>>>>>>>>>>>> inbetween), does this genuinely imply that the calculation >>>>>>>>>>>>>>> will >>>>>>>>>>>>>>> never >>>>>>>>>>>>>>> halt? >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Bear in mind that the two calls in question do not >>>>>>>>>>>>>>> necessarily >>>>>>>>>>>>>>> occur in >>>>>>>>>>>>>>> the same "virtual address space", that is to say the two >>>>>>>>>>>>>>> calls can >>>>>>>>>>>>>>> [and >>>>>>>>>>>>>>> in the case of T_Hat(T_Hat) *do* ] occur at /different >>>>>>>>>>>>>>> levels of >>>>>>>>>>>>>>> emulation/. [Your trace notation obscures this simple >>>>>>>>>>>>>>> fact, >>>>>>>>>>>>>>> making >>>>>>>>>>>>>>> everything appear to be in one single virtual process, when >>>>>>>>>>>>>>> it's >>>>>>>>>>>>>>> not.] >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> What do you think? This seems to be your primary intuition >>>>>>>>>>>>>>> that >>>>>>>>>>>>>>> triggered all this "refuting" activity, BUT IS IT ACTUALLY >>>>>>>>>>>>>>> CORRECT? >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Of course, you will say "All my intuitions are correct by >>>>>>>>>>>>>>> definition - >>>>>>>>>>>>>>> I'm never wrong" but that doesn't make it true! :) >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Is TEST *SOUND* ? >>>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> Noted: still no response to this basic question. >>>>>>>>>>>>>> >>>>>>>>>>>>>> Mike. >>>>>>>>>>>>>> >>>>>>>>>>>> <.. snip non-response to question ..> >>>>>>>>>>>> >>>>>>>>>>>> I'm not sure if that non-response was deliberate. I didn't ask >>>>>>>>>>>> whether one specified implementation of [whatever] exhibits >>>>>>>>>>>> infinite >>>>>>>>>>>> recursion! >>>>>>>>>>>> >>>>>>>>>>>> In case it was just a misreading, here is the question again. >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> So... what do you think. Is the following test a SOUND >>>>>>>>>>>> test >>>>>>>>>>>> for >>>>>>>>>>>> non-halting? >>>>>>>>>>>> >>>>>>>>>>>> TEST: "monitor the simulation until there is a function >>>>>>>>>>>> call to 377 from 503 a second time, with no >>>>>>>>>>>> conditional >>>>>>>>>>>> branch in-between" >>>>>>>>>>> >>>>>>>>>>> It is much more generic than that. >>>>>>>>>>> (1) Keep a global execution trace of every line of user code. >>>>>>>>>>> >>>>>>>>>>> (2) Whenever any instruction is executed see if it is a function >>>>>>>>>>> call. >>>>>>>>>>> >>>>>>>>>>> (3) If it is a function call find the prior call to this same >>>>>>>>>>> function >>>>>>>>>>> from the current machine address (if any) searching backward >>>>>>>>>>> through the >>>>>>>>>>> global execution trace and counting conditional branch >>>>>>>>>>> instructions. >>>>>>>>>>> >>>>>>>>>>> (4) If found and conditional-branch-count == zero terminate the >>>>>>>>>>> input. >>>>>>>>>>> >>>>>>>>>>> Copyright 2020 Pete Olcott (I just wrote that algorithm right >>>>>>>>>>> now). >>>>>>>>>> >>>>>>>>>> OK, I always imagined the test would be more general than just >>>>>>>>>> checking specifically for calls to 377 from 503. :) No >>>>>>>>>> problem on >>>>>>>>>> that front. >>>>>>>>>> >>>>>>>>>> I'm thinking this is probably the basis of your initial intuition >>>>>>>>>> that >>>>>>>>>> you could actually detect and handle the type of recursion in >>>>>>>>>> your >>>>>>>>>> fledgeling (at that time) halt decider design. >>>>>>>>>> >>>>>>>>>> It is good that you've clarified the test, and yet it seems >>>>>>>>>> you're >>>>>>>>>> reluctant to plainly say that you believe the test works! >>>>>>>>> >>>>>>>>> logical necessity speaks for itself it doesn't need me for a >>>>>>>>> cheerleader. >>>>>>>>> >>>>>>>> >>>>>>>> LOL. I knew you'd do something like that. >>>>>>>> >>>>>>>> OK, so you are saying that if your test detects the behaviour >>>>>>>> described, then it's a "logical necessity" that the input being >>>>>>>> examined is non-halting? >>>>>>> >>>>>>> Yes that is what I am saying. >>>>>> >>>>>> There - that wasn't so bad, was it? :) >>>>>> >>>>>>> >>>>>>> Can you find a counter-example? >>>>>> >>>>>> Well, if it's a logical necessity I'm in for a hard time on that >>>>>> one... >>>>>> >>>>>> But here's the point: logical necessity absolutely /does/ need a >>>>>> cheerleader! Loads of things are "logically necessary" in that they >>>>>> must logically be true, and yet they are not /obviously/ true. >>>>>> That's >>>>>> why we have proofs. >>>>>> >>>>>> This would be one of those scenarios, where even if your claim is >>>>>> correct, it's not trivially obvious that it's correct, right? >>>>>> >>>>>> Here is what we're saying: >>>>>> >>>>>> TEST: >>>>>> If a calculation P(I) has a trace of steps >>>>>> (s0, s1, s2, s3, .....) and there are two steps s_i >>>>>> and s_j, such that si and sj are both unconditional >>>>>> branches from A to B, and none of the steps in-between >>>>>> s_i and s_j are conditional branches, THEN calculation >>>>>> P(I) never halts. >>>>>> >>>>>> Well that's certainly not a "trivial restatement of word meanings" or >>>>>> similar, and so is not seen to correct just on a casual glance. >>>>>> >>>>>> So obviously where I'm going is : do you have a proof of this? >>>>>> >>>>>> Now I know you're not one for proofs, and maybe during the course of >>>>>> discussion such a proof will fall out (provided the underlying logic >>>>>> is correct...) >>>>>> >>>>>> So to start with, perhaps you can just give your thinking as to /why/ >>>>>> you believe it to be logically necessary? [You clearly didn't >>>>>> wake up >>>>>> one day and think "hey, what about TEST - oh! it's a logical >>>>>> necessity, that's handy - I can use it in my halt decider!". There >>>>>> was something that led you to consider TEST, and having considered >>>>>> it, >>>>>> you decided for whatever reason it was true...] >>>>>> >>>>>> >>>>>> Mike. >>>>>> >>>>> >>>>> Let's look at it a little simpler: >>>>> HERE: // current location >>>>> Instructions that cannot possibly exit a loop >>>>> THERE: goto HERE; >>>>> >>>>> Can you see how this definitely loops? >>>> >>>> I can - and if this was relevant there would be a straight forward >>>> proof that such code loops. >>>> >>>> But this isn't like the scenario you are dealing with AT ALL! What >>>> you are showing here is a kind of "in-process" loop detection. What >>>> you need is some kind of recursive EMULATION detection. (Emulation >>>> works differently in this respect.) >>>> >>>> I'm pretty sure I explained the difference in a post a couple of weeks >>>> ago but you never responded. >>> >>> We are trying to determine whether or not a specific sequence of x86 >>> machine code bytes specify an infinite loop as if this machine code was >>> a mathematical formalism. >>> >>> The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY? >>> >> >> Well, I understand that the code bytes that you presented, if executed >> by a processor within one single logical thread of execution, would >> never terminate - there is an obvious loop. >> >> But that's ignoring the issue of RECURSION, where behaviour is not so >> simple. So what's the next step? (So far what you've said is no >> justification for the RECUSION scenario, which is what you TEST is >> concerned with.) >> >> Mike. >> > > The sequences of instructions from HERE to THERE and HERE to HERE are > from actual execution traces. The x86 emulator screens out all dead code > and only shows us the code that is actually reached. > > -HERE: // current location > - Instructions that cannot possibly exit a loop > -THERE: goto HERE; > > To form a mathematical proof on the basis of the x86 language being > construed as a formal language we only have to derive the complete list > of every instruction that can possibly exit the above loop and if there > are none of these between the labels HERE and THERE then we know that > the loop is infinite. Like I said, that is ok for a "contiguous thread of execution", i.e. if an x86 processor starts at HERE, and then steps its execution, executing the instructions, then the processor will go round and round the loop. The proof is easy. > > The case for infinite recursion is similar. No it's not. The easy proof for the contiguous thread of execution does not work in the case where there is recursion. Or, put more accurately, it works WITHIN A SINGLE CONTIGUOUS THREAD OF EXECUTION (the obvious proof still works for this), but *NOT WHEN THE TRACE ENTRIES CROSS RECURSION LEVELS*. > > -HERE: Call Function At Address X > - Instructions that cannot possibly exit recursion > -HERE: Call Function At Address X > > If there are no instructions that can possibly exit recursion between > invocations of the same function from the same machine address, then > recursion is infinite. That doesn't work with recursive emulation, BECAUSE THE EMULATION CAN BE BROKEN FROM OUTSIDE THE SET OF INSTRUCTIONS YOU ARE CONSIDERING. Mike.
[toc] | [prev] | [next] | [standalone]
Page 5 of 11 — ← Prev page 1 … 3 4 [5] 6 7 … 11 Next page →
Back to top | Article view | comp.theory
csiph-web