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 8 of 11 — ← Prev page 1 … 6 7 [8] 9 10 11 Next page →
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-11-26 17:49 -0500 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language) |
| Message-ID | <RhWvH.11062$lP1.8733@fx37.iad> |
| In reply to | #26059 |
On 11/26/20 4:31 PM, olcott wrote:
> On 11/26/2020 3:14 PM, Richard Damon wrote:
>> On 11/26/20 3:50 PM, olcott wrote:
>>>
>>>
>>> That could simply be thought of as recursive invocation that is
>>> functionally equivalent to this:
>>>
>>> int DebugTrace(u32 P, u32 I)
>>> {
>>> ((int(*)(int))P)(I);
>>> return 1;
>>> }
>>>
>>> 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;
>>> }
>>
>> One thing that I have realized as I am thinking on this, your 'trace' of
>> execution NEEDS to include, or at least acknowledge the operation of the
>> Halts code when that call occurs when under emulation.
>>
>> That is part of the issue with your logic, by removing that from the
>> trace, you are loosing come of the actions that are actually part of the
>> computations being traced.
>
> The operating system already knows that it does not have any infinite
> execution.
But it creates it. H_Hat in its basic definition is NOT recursiove, it
is self-referential. It is only the fact that your particular Halt
decider works by pure execution that causes ANY recursion to occur, let
alone the infinite recursion that it needs to fix itself.
>
>> Maybe it doesn't need to show all the gritty details, but at least the
>> fact that is didn't abort / did abort indication (with an indication of
>> what level was making that decision, so multiple lines might report)
>
> Any person looking at an execution trace that includes two calls to the
> same function from the same machine address that does not have any
> conditional branch instruction in-between that could possibly break out
> of this infinite recursion knows the infinite recursion has been detected.
>
But if you look at the ACTUAL execution trace of the processor, you will
see that there ARE conditional branches in the exectution path, and that
at least some of these are part of the computation defined by the
machine being run.
>
> 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;
Yes, if that TRUELY is the code being run, then we have an infinite loop.
>
> 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.
I don't think you have the background to make a real formal proof of
this. Note, that wnen you start to work on this, you need to include ALL
the software that is running. One thing you seem to keep on dropping is
that once we are executing inside a Halts call that is part of the
computation, the defined action of that Halts call are part of the
defined behavior of the system. By ignoring it, you are making unsound
arguments.
Remember, the reason Turing Machines were invented was to have simpler
machine to be able to argue with.
>
> 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.
Except, as I pointed out, if this is running inside a Halts that is part
of the computation, then the conditionals inside that Halts call need to
be taken account of.
For example, the following is a proper finite computation (given a
working halts)
void looper(u32 I)
{
while(1) ;
}
void tester(u32 P)
{
Halts(P, P);
HALT;
}
int main() {
u32 P = (U32)looper;
tester(P);
}
While doing a trace like you have been doing, it will be clear that we
have an infinite loop inside looper, which is within the trace of
ttester, but the fact that it is inside a Halts call, says that that
infinite loop inside looper doesn't cause tester to be non-halting.
The infinite loop inside looper isn't really that fundamentally
different than the recursion loop setup in H_Hat.
By your reasoning, it would seem that any program that uses the halt
decider on another program that happens to be non-halting becomes a
non-halting program.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-26 17:01 -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 | <BuSdneS69aMhrl3CnZ2dnUU7-bXNnZ2d@giganews.com> |
| In reply to | #26069 |
On 11/26/2020 4:49 PM, Richard Damon wrote:
> On 11/26/20 4:31 PM, olcott wrote:
>> On 11/26/2020 3:14 PM, Richard Damon wrote:
>>> On 11/26/20 3:50 PM, olcott wrote:
>>>>
>>>>
>>>> That could simply be thought of as recursive invocation that is
>>>> functionally equivalent to this:
>>>>
>>>> int DebugTrace(u32 P, u32 I)
>>>> {
>>>> ((int(*)(int))P)(I);
>>>> return 1;
>>>> }
>>>>
>>>> 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;
>>>> }
>>>
>>> One thing that I have realized as I am thinking on this, your 'trace' of
>>> execution NEEDS to include, or at least acknowledge the operation of the
>>> Halts code when that call occurs when under emulation.
>>>
>>> That is part of the issue with your logic, by removing that from the
>>> trace, you are loosing come of the actions that are actually part of the
>>> computations being traced.
>>
>> The operating system already knows that it does not have any infinite
>> execution.
>
> But it creates it. H_Hat in its basic definition is NOT recursiove, it
> is self-referential. It is only the fact that your particular Halt
> decider works by pure execution that causes ANY recursion to occur, let
> alone the infinite recursion that it needs to fix itself.
Any input (TMD / DATA) that would never halt unless its (UTM) stopped
simulating it expresses behavior that is not halting behavior.
When Halts() simulates its input (playing the exact same role as the
above UTM) then any "not halting" decision that it makes according to
the above criteria would be necessarily correct.
Halts(H_Hat, H_Hat) is such a "not halting" decision.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-29 16:33 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <3_ydnRQlSJY8vFnCnZ2dnUU7-L3NnZ2d@giganews.com> |
| In reply to | #26034 |
On 11/26/2020 11:08 AM, Mike Terry wrote: > On 26/11/2020 16:41, olcott wrote: >> On 11/26/2020 10:30 AM, Mike Terry wrote: >>> 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. >>> >> >> That doesn't count. We are only examining the execution that is >> specified by the actual x86 language bytes as a formal language of a >> formal system. > > Eh? Of course it counts. If you see a pattern of trace entries where > that pattern can be broken from outside the block you are considering, > then that does not mean that the pattern of the block will continue > indefinitely. > > I think you're ignoring the fact that recursive emulation can be broken > by an OUTER LEVEL of recursion "aborting" the inner levels. > > Mike. The following proves that recursive emulation is computationally equivalent to recursive invocation: UTM1(<TM1>, DATA) ≡ TM1(DATA) ∴ UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) So we can subtract the emulation detail as extraneous and merely examine the recursive invocation. This brings us back to (right where we were) with the halt decider recognizing and aborting infinitely recursive invocation. -- 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-30 00:38 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <lsednciM6c6VolnCnZ2dnUU78X_NnZ2d@brightview.co.uk> |
| In reply to | #26202 |
On 29/11/2020 22:33, olcott wrote: > On 11/26/2020 11:08 AM, Mike Terry wrote: >> On 26/11/2020 16:41, olcott wrote: >>> On 11/26/2020 10:30 AM, Mike Terry wrote: >>>> 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. >>>> >>> >>> That doesn't count. We are only examining the execution that is >>> specified by the actual x86 language bytes as a formal language of a >>> formal system. >> >> Eh? Of course it counts. If you see a pattern of trace entries where >> that pattern can be broken from outside the block you are considering, >> then that does not mean that the pattern of the block will continue >> indefinitely. >> >> I think you're ignoring the fact that recursive emulation can be >> broken by an OUTER LEVEL of recursion "aborting" the inner levels. >> >> Mike. > > The following proves that recursive emulation is computationally > equivalent to recursive invocation: > > UTM1(<TM1>, DATA) ≡ TM1(DATA) > ∴ > UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) > > So we can subtract the emulation detail as extraneous and merely examine > the recursive invocation. > > This brings us back to (right where we were) with the halt decider > recognizing and aborting infinitely recursive invocation. No. We are talking about EMULATION, not specifically UTMs. Emulators can choose to abort execution of their inputs. (UTMs just emulate until their input halts.) Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-29 19:16 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <2s6dnehj0tVT2lnCnZ2dnUU7-IfNnZ2d@giganews.com> |
| In reply to | #26204 |
On 11/29/2020 6:38 PM, Mike Terry wrote: > On 29/11/2020 22:33, olcott wrote: >> On 11/26/2020 11:08 AM, Mike Terry wrote: >>> On 26/11/2020 16:41, olcott wrote: >>>> On 11/26/2020 10:30 AM, Mike Terry wrote: >>>>> 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. >>>>> >>>> >>>> That doesn't count. We are only examining the execution that is >>>> specified by the actual x86 language bytes as a formal language of a >>>> formal system. >>> >>> Eh? Of course it counts. If you see a pattern of trace entries where >>> that pattern can be broken from outside the block you are considering, >>> then that does not mean that the pattern of the block will continue >>> indefinitely. >>> >>> I think you're ignoring the fact that recursive emulation can be >>> broken by an OUTER LEVEL of recursion "aborting" the inner levels. >>> >>> Mike. >> >> The following proves that recursive emulation is computationally >> equivalent to recursive invocation: >> >> UTM1(<TM1>, DATA) ≡ TM1(DATA) >> ∴ >> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) >> >> So we can subtract the emulation detail as extraneous and merely examine >> the recursive invocation. >> >> This brings us back to (right where we were) with the halt decider >> recognizing and aborting infinitely recursive invocation. > > No. We are talking about EMULATION, not specifically UTMs. Emulators > can choose to abort execution of their inputs. (UTMs just emulate until > their input halts.) > > > Mike. None of these details any effect on correctly deciding not halting for both the x86 virtual machine H_Hat and its equivalent Turing machine description on the basis of this emulation. I got both infinite recursion and infinite loop detection fully operational today. -- 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-30 02:38 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <262dnU6IlqGNxlnCnZ2dnUU78dHNnZ2d@brightview.co.uk> |
| In reply to | #26205 |
On 30/11/2020 01:16, olcott wrote: > On 11/29/2020 6:38 PM, Mike Terry wrote: >> On 29/11/2020 22:33, olcott wrote: >>> On 11/26/2020 11:08 AM, Mike Terry wrote: >>>> On 26/11/2020 16:41, olcott wrote: >>>>> On 11/26/2020 10:30 AM, Mike Terry wrote: >>>>>> 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. >>>>>> >>>>> >>>>> That doesn't count. We are only examining the execution that is >>>>> specified by the actual x86 language bytes as a formal language of a >>>>> formal system. >>>> >>>> Eh? Of course it counts. If you see a pattern of trace entries where >>>> that pattern can be broken from outside the block you are considering, >>>> then that does not mean that the pattern of the block will continue >>>> indefinitely. >>>> >>>> I think you're ignoring the fact that recursive emulation can be >>>> broken by an OUTER LEVEL of recursion "aborting" the inner levels. >>>> >>>> Mike. >>> >>> The following proves that recursive emulation is computationally >>> equivalent to recursive invocation: >>> >>> UTM1(<TM1>, DATA) ≡ TM1(DATA) >>> ∴ >>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) >>> >>> So we can subtract the emulation detail as extraneous and merely examine >>> the recursive invocation. >>> >>> This brings us back to (right where we were) with the halt decider >>> recognizing and aborting infinitely recursive invocation. >> >> No. We are talking about EMULATION, not specifically UTMs. Emulators >> can choose to abort execution of their inputs. (UTMs just emulate >> until their input halts.) >> >> >> Mike. > > None of these details any effect on correctly deciding not halting for > both the x86 virtual machine H_Hat and its equivalent Turing machine > description on the basis of this emulation. So it sounds like you're giving up on your claim that your test is sound. (An unsound test can still make correct decisions, but in the case of input (H_Hat,H_Hat) the unsound test makes an incorrect decision.) > > I got both infinite recursion and infinite loop detection fully > operational today. Infinite loop detection (within a single virtual process) /could/ be working, since that is a fairly straight forward test, in principle at least. (I don't know if your trace mechanism makes it easy or hard - I suggested the trace needs an "emulation ID" column, and without that how would you know trace entries are in the same VP? You didn't seem to think an ID was needed, so you could just be confused even with your loop detection...) Your infinite recursion test is unsound, so is effectively worthless. Sometimes it will work, and sometimes not - but the important thing is you cannot claim that /because/ it thought it found infinite recursion that means there really /was/ infinite recursion. It's a test that you may as well describe as "seeing something it doesn't like". (You disagreed violently when I first suggested that, but now it seems you've come around to that position. Or maybe not, hard to tell what you're agreeing or disagreeing with.) Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-29 21:12 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <eIydnXwgZaqU_lnCnZ2dnUU7-LPNnZ2d@giganews.com> |
| In reply to | #26211 |
On 11/29/2020 8:38 PM, Mike Terry wrote: > On 30/11/2020 01:16, olcott wrote: >> On 11/29/2020 6:38 PM, Mike Terry wrote: >>> On 29/11/2020 22:33, olcott wrote: >>>> On 11/26/2020 11:08 AM, Mike Terry wrote: >>>>> On 26/11/2020 16:41, olcott wrote: >>>>>> On 11/26/2020 10:30 AM, Mike Terry wrote: >>>>>>> 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. >>>>>>> >>>>>> >>>>>> That doesn't count. We are only examining the execution that is >>>>>> specified by the actual x86 language bytes as a formal language of a >>>>>> formal system. >>>>> >>>>> Eh? Of course it counts. If you see a pattern of trace entries where >>>>> that pattern can be broken from outside the block you are considering, >>>>> then that does not mean that the pattern of the block will continue >>>>> indefinitely. >>>>> >>>>> I think you're ignoring the fact that recursive emulation can be >>>>> broken by an OUTER LEVEL of recursion "aborting" the inner levels. >>>>> >>>>> Mike. >>>> >>>> The following proves that recursive emulation is computationally >>>> equivalent to recursive invocation: >>>> >>>> UTM1(<TM1>, DATA) ≡ TM1(DATA) >>>> ∴ >>>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) >>>> >>>> So we can subtract the emulation detail as extraneous and merely >>>> examine >>>> the recursive invocation. >>>> >>>> This brings us back to (right where we were) with the halt decider >>>> recognizing and aborting infinitely recursive invocation. >>> >>> No. We are talking about EMULATION, not specifically UTMs. Emulators >>> can choose to abort execution of their inputs. (UTMs just emulate >>> until their input halts.) >>> >>> >>> Mike. >> >> None of these details any effect on correctly deciding not halting for >> both the x86 virtual machine H_Hat and its equivalent Turing machine >> description on the basis of this emulation. > > So it sounds like you're giving up on your claim that your test is > sound. (An unsound test can still make correct decisions, but in the > case of input (H_Hat,H_Hat) the unsound test makes an incorrect decision.) You provided no basis what-so-ever to show that my reasoning is unsound and as of today I have fully operational code proving that it is sound. >> >> I got both infinite recursion and infinite loop detection fully >> operational today. > > Infinite loop detection (within a single virtual process) /could/ be > working, since that is a fairly straight forward test, in principle at > least. (I don't know if your trace mechanism makes it easy or hard - I It takes one page of C++ code to detect infinite recursion to any arbitrary depth: A calls B calls C calls D calls A and the same one page of code detects infinite loops. > suggested the trace needs an "emulation ID" column, and without that how > would you know trace entries are in the same VP? You didn't seem to > think an ID was needed, so you could just be confused even with your > loop detection...) So in other words you still don't understand that recursive emulation is computationally equivalent to recursive invocation thus a detail that can be abstracted away without effect on correct halt deciding? UTM1(<TM1>, DATA) ≡ TM1(DATA) ∴ UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) > Your infinite recursion test is unsound, so is effectively worthless. > Sometimes it will work, Any idiot can make assertions (like this) that are utterly bereft of any supporting reasoning. I can objectively say that this assertion is literally baseless. Has is come down to that? If you can't show any actual error you will still claim that I am wrong for some reason that is unspecified because it is non-existent? > and sometimes not - but the important thing is > you cannot claim that /because/ it thought it found infinite recursion > that means there really /was/ infinite recursion. Sure any who know by this same reasoning maybe someone will find a natural number w such that (w > 5) ∧ (w < 3). ∀n ∈ ℕ ((n > 5) → (N > 3)) > It's a test that you > may as well describe as "seeing something it doesn't like". (You That ridiculous way of saying it is like saying that this logic expression: ∀n ∈ ℕ ((n > 5) → (N > 3)) "doesn't like" natural numbers that are less than five. > disagreed violently when I first suggested that, but now it seems you've > come around to that position. Or maybe not, hard to tell what you're > agreeing or disagreeing with.) > > > 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-30 03:23 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <Rp6dnb7ZyLcm-FnCnZ2dnUU78bHNnZ2d@brightview.co.uk> |
| In reply to | #26214 |
On 30/11/2020 03:12, olcott wrote: > On 11/29/2020 8:38 PM, Mike Terry wrote: >> On 30/11/2020 01:16, olcott wrote: >>> On 11/29/2020 6:38 PM, Mike Terry wrote: >>>> On 29/11/2020 22:33, olcott wrote: >>>>> On 11/26/2020 11:08 AM, Mike Terry wrote: >>>>>> On 26/11/2020 16:41, olcott wrote: >>>>>>> On 11/26/2020 10:30 AM, Mike Terry wrote: >>>>>>>> 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. >>>>>>>> >>>>>>> >>>>>>> That doesn't count. We are only examining the execution that is >>>>>>> specified by the actual x86 language bytes as a formal language of a >>>>>>> formal system. >>>>>> >>>>>> Eh? Of course it counts. If you see a pattern of trace entries >>>>>> where >>>>>> that pattern can be broken from outside the block you are >>>>>> considering, >>>>>> then that does not mean that the pattern of the block will continue >>>>>> indefinitely. >>>>>> >>>>>> I think you're ignoring the fact that recursive emulation can be >>>>>> broken by an OUTER LEVEL of recursion "aborting" the inner levels. >>>>>> >>>>>> Mike. >>>>> >>>>> The following proves that recursive emulation is computationally >>>>> equivalent to recursive invocation: >>>>> >>>>> UTM1(<TM1>, DATA) ≡ TM1(DATA) >>>>> ∴ >>>>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) >>>>> >>>>> So we can subtract the emulation detail as extraneous and merely >>>>> examine >>>>> the recursive invocation. >>>>> >>>>> This brings us back to (right where we were) with the halt decider >>>>> recognizing and aborting infinitely recursive invocation. >>>> >>>> No. We are talking about EMULATION, not specifically UTMs. Emulators >>>> can choose to abort execution of their inputs. (UTMs just emulate >>>> until their input halts.) >>>> >>>> >>>> Mike. >>> >>> None of these details any effect on correctly deciding not halting for >>> both the x86 virtual machine H_Hat and its equivalent Turing machine >>> description on the basis of this emulation. >> >> So it sounds like you're giving up on your claim that your test is >> sound. (An unsound test can still make correct decisions, but in the >> case of input (H_Hat,H_Hat) the unsound test makes an incorrect >> decision.) > > You provided no basis what-so-ever to show that my reasoning is unsound > and as of today I have fully operational code proving that it is sound. > >>> >>> I got both infinite recursion and infinite loop detection fully >>> operational today. >> >> Infinite loop detection (within a single virtual process) /could/ be >> working, since that is a fairly straight forward test, in principle at >> least. (I don't know if your trace mechanism makes it easy or hard - I > > It takes one page of C++ code to detect infinite recursion to any > arbitrary depth: A calls B calls C calls D calls A > and the same one page of code detects infinite loops. > >> suggested the trace needs an "emulation ID" column, and without that >> how would you know trace entries are in the same VP? You didn't seem >> to think an ID was needed, so you could just be confused even with >> your loop detection...) > > So in other words you still don't understand that recursive emulation is > computationally equivalent to recursive invocation thus a detail that > can be abstracted away without effect on correct halt deciding? > > UTM1(<TM1>, DATA) ≡ TM1(DATA) > ∴ > UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) <yawn> Now you're just repeating over and over. > >> Your infinite recursion test is unsound, so is effectively worthless. >> Sometimes it will work, > > Any idiot can make assertions (like this) that are utterly bereft of any > supporting reasoning. I can objectively say that this assertion is > literally baseless. Has is come down to that? > > If you can't show any actual error you will still claim that I am wrong > for some reason that is unspecified because it is non-existent? YOU are the one making a claim - so YOU have to prove your claim. It's quite ok with me if you don't. But you shouldn't boast about stuff you've not proved. I suppose in the end it comes down to you /believing/ you've proved all sorts of stuff, and /believing/ that nobody has refuted anything you've said. Everyone else is of the opinion that you're a Deluded Dumbo, who gets even the simplest of things wrong, and can't follow the explanations given as to why you're wrong. Sort of a stalemate, but comp.theory doesn't matter - time for you to publish, and then you'll have the last laugh (if you're right...) Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-29 21:53 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <RaudnenhwPkD8VnCnZ2dnUU7-KfNnZ2d@giganews.com> |
| In reply to | #26215 |
On 11/29/2020 9:23 PM, Mike Terry wrote:
> On 30/11/2020 03:12, olcott wrote:
>> On 11/29/2020 8:38 PM, Mike Terry wrote:
>>> On 30/11/2020 01:16, olcott wrote:
>>>> On 11/29/2020 6:38 PM, Mike Terry wrote:
>>>>> On 29/11/2020 22:33, olcott wrote:
>>>>>> On 11/26/2020 11:08 AM, Mike Terry wrote:
>>>>>>> On 26/11/2020 16:41, olcott wrote:
>>>>>>>> On 11/26/2020 10:30 AM, Mike Terry wrote:
>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>
>>>>>>>> That doesn't count. We are only examining the execution that is
>>>>>>>> specified by the actual x86 language bytes as a formal language
>>>>>>>> of a
>>>>>>>> formal system.
>>>>>>>
>>>>>>> Eh? Of course it counts. If you see a pattern of trace entries
>>>>>>> where
>>>>>>> that pattern can be broken from outside the block you are
>>>>>>> considering,
>>>>>>> then that does not mean that the pattern of the block will continue
>>>>>>> indefinitely.
>>>>>>>
>>>>>>> I think you're ignoring the fact that recursive emulation can be
>>>>>>> broken by an OUTER LEVEL of recursion "aborting" the inner levels.
>>>>>>>
>>>>>>> Mike.
>>>>>>
>>>>>> The following proves that recursive emulation is computationally
>>>>>> equivalent to recursive invocation:
>>>>>>
>>>>>> UTM1(<TM1>, DATA) ≡ TM1(DATA)
>>>>>> ∴
>>>>>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA))
>>>>>>
>>>>>> So we can subtract the emulation detail as extraneous and merely
>>>>>> examine
>>>>>> the recursive invocation.
>>>>>>
>>>>>> This brings us back to (right where we were) with the halt decider
>>>>>> recognizing and aborting infinitely recursive invocation.
>>>>>
>>>>> No. We are talking about EMULATION, not specifically UTMs. Emulators
>>>>> can choose to abort execution of their inputs. (UTMs just emulate
>>>>> until their input halts.)
>>>>>
>>>>>
>>>>> Mike.
>>>>
>>>> None of these details any effect on correctly deciding not halting for
>>>> both the x86 virtual machine H_Hat and its equivalent Turing machine
>>>> description on the basis of this emulation.
>>>
>>> So it sounds like you're giving up on your claim that your test is
>>> sound. (An unsound test can still make correct decisions, but in the
>>> case of input (H_Hat,H_Hat) the unsound test makes an incorrect
>>> decision.)
>>
>> You provided no basis what-so-ever to show that my reasoning is unsound
>> and as of today I have fully operational code proving that it is sound.
>>
>>>>
>>>> I got both infinite recursion and infinite loop detection fully
>>>> operational today.
>>>
>>> Infinite loop detection (within a single virtual process) /could/ be
>>> working, since that is a fairly straight forward test, in principle at
>>> least. (I don't know if your trace mechanism makes it easy or hard - I
>>
>> It takes one page of C++ code to detect infinite recursion to any
>> arbitrary depth: A calls B calls C calls D calls A
>> and the same one page of code detects infinite loops.
>>
>>> suggested the trace needs an "emulation ID" column, and without that
>>> how would you know trace entries are in the same VP? You didn't seem
>>> to think an ID was needed, so you could just be confused even with
>>> your loop detection...)
>>
>> So in other words you still don't understand that recursive emulation is
>> computationally equivalent to recursive invocation thus a detail that
>> can be abstracted away without effect on correct halt deciding?
>>
>> UTM1(<TM1>, DATA) ≡ TM1(DATA)
>> ∴
>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA))
>
> <yawn> Now you're just repeating over and over.
OK then you both understand and agree that I am correct about this.
>>
>>> Your infinite recursion test is unsound, so is effectively worthless.
>>> Sometimes it will work,
>>
>> Any idiot can make assertions (like this) that are utterly bereft of any
>> supporting reasoning. I can objectively say that this assertion is
>> literally baseless. Has is come down to that?
>>
>> If you can't show any actual error you will still claim that I am wrong
>> for some reason that is unspecified because it is non-existent?
>
> YOU are the one making a claim - so YOU have to prove your claim.
I have proved my claim and you vaguely say that there is an error
somewhere yet don't point it out because you are not actually aware of
any error.
>
> It's quite ok with me if you don't. But you shouldn't boast about stuff
> you've not proved.
>
I have totally proved these things and people are unable to find any
flaws in my proofs, yet disagree simply out of habit.
> I suppose in the end it comes down to you /believing/ you've proved all
> sorts of stuff, and /believing/ that nobody has refuted anything you've
> said. Everyone else is of the opinion that you're a Deluded Dumbo, who
> gets even the simplest of things wrong, and can't follow the
> explanations given as to why you're wrong.
That is just the kind of utterly baseless things that people say when
they run out of any logical basis yet still want to contrive a rebuttal.
> Sort of a stalemate, but comp.theory doesn't matter - time for you to
> publish, and then you'll have the last laugh (if you're right...)
>
>
> Mike.
>
You claimed that my specific algorithm is incorrect
(here it is fully encoded)
if (loc.Simplified_Opcode == CALL)
if (loc.Simplified_Opcode == traced.Simplified_Opcode)
if (loc.Address == traced.Address)
if (loc.Decode_Target == traced.Decode_Target)
if (Count_Conditional_Branch_Instructions == 0)
yet could not point out any actual error. In place of reasoning all you
have is rhetoric.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2020-11-29 21:31 -0700 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <rq1sit$spi$1@dont-email.me> |
| In reply to | #26216 |
On 11/29/2020 8:53 PM, olcott wrote:
> On 11/29/2020 9:23 PM, Mike Terry wrote:
>> On 30/11/2020 03:12, olcott wrote:
>>> On 11/29/2020 8:38 PM, Mike Terry wrote:
<big snip>
> You claimed that my specific algorithm is incorrect
> (here it is fully encoded)
>
> if (loc.Simplified_Opcode == CALL)
> if (loc.Simplified_Opcode == traced.Simplified_Opcode)
> if (loc.Address == traced.Address)
> if (loc.Decode_Target == traced.Decode_Target)
> if (Count_Conditional_Branch_Instructions == 0)
>
> yet could not point out any actual error. In place of reasoning all you
> have is rhetoric.
Since none of these terms/fields are defined this snippet is as vacuous
as your head is empty. The only logical deduction I can make is the
following:
CALL == traced.simplified_Opcode
is necessary for execution to reach the third IF predicate. Just
curious, is this TRUE? I'm also curious whether this nested IF does
anything, ever? It seems to end without any sort of ELSE like action. If
I understand this snippet, I am convinced that your lack of programming
skill is abundantly demonstrated just as I inferred from your many posts
in these threads.
--
Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-11-30 21:28 +0000 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <6cWdnZg6Fr2X-VjCnZ2dnUU78fPNnZ2d@brightview.co.uk> |
| In reply to | #26216 |
On 30/11/2020 03:53, olcott wrote: > On 11/29/2020 9:23 PM, Mike Terry wrote: >> On 30/11/2020 03:12, olcott wrote: >>> On 11/29/2020 8:38 PM, Mike Terry wrote: <.. snip ..> >>>> >>>> Infinite loop detection (within a single virtual process) /could/ be >>>> working, since that is a fairly straight forward test, in principle at >>>> least. (I don't know if your trace mechanism makes it easy or hard - I >>> >>> It takes one page of C++ code to detect infinite recursion to any >>> arbitrary depth: A calls B calls C calls D calls A >>> and the same one page of code detects infinite loops. >>> >>>> suggested the trace needs an "emulation ID" column, and without that >>>> how would you know trace entries are in the same VP? You didn't seem >>>> to think an ID was needed, so you could just be confused even with >>>> your loop detection...) >>> >>> So in other words you still don't understand that recursive emulation is >>> computationally equivalent to recursive invocation thus a detail that >>> can be abstracted away without effect on correct halt deciding? >>> >>> UTM1(<TM1>, DATA) ≡ TM1(DATA) >>> ∴ >>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA)) >> >> <yawn> Now you're just repeating over and over. > > OK then you both understand and agree that I am correct about this. > When someone disagrees with you, and you simply repeat yourself again, then you can safely assume they still disagree with you. <.. snip more repetitions of "I'm right, you're wrong" ..> > > You claimed that my specific algorithm is incorrect > (here it is fully encoded) > > if (loc.Simplified_Opcode == CALL) > if (loc.Simplified_Opcode == traced.Simplified_Opcode) > if (loc.Address == traced.Address) > if (loc.Decode_Target == traced.Decode_Target) > if (Count_Conditional_Branch_Instructions == 0) > > yet could not point out any actual error. In place of reasoning all you > have is rhetoric. What do you expect me to do with your code? Your algorithm is claiming to do something that is in fact impossible - pointing out an "actual error" would suggest you just have a bug, and when I correct that bug for you it will work. Well, it won't because what is wrong is your underlying intuition that you can spot infinite recursive emulation with your TEST. Also, I explained where your "proof" went wrong, but you since you don't really understand what a proof should be anyway, it was a bit of a waste of time. Actually, I was being overly generous when I said your proof only worked in a single-process trace context. You had not actually provided a "proof" that worked even for that environment. Maybe if you understood how that proof worked, you might have a chance of understanding why it doesn't work for an emulation trace context. Or perhaps try to construct your own counter-example for TEST. Mike.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 15:31 -0600 |
| Subject | 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) |
| Message-ID | <MMmdndd0uI0K-VjCnZ2dnUU7-f-dnZ2d@giganews.com> |
| In reply to | #26232 |
On 11/30/2020 3:28 PM, Mike Terry wrote:
> On 30/11/2020 03:53, olcott wrote:
>> On 11/29/2020 9:23 PM, Mike Terry wrote:
>>> On 30/11/2020 03:12, olcott wrote:
>>>> On 11/29/2020 8:38 PM, Mike Terry wrote:
> <.. snip ..>
>>>>>
>>>>> Infinite loop detection (within a single virtual process) /could/ be
>>>>> working, since that is a fairly straight forward test, in principle at
>>>>> least. (I don't know if your trace mechanism makes it easy or hard
>>>>> - I
>>>>
>>>> It takes one page of C++ code to detect infinite recursion to any
>>>> arbitrary depth: A calls B calls C calls D calls A
>>>> and the same one page of code detects infinite loops.
>>>>
>>>>> suggested the trace needs an "emulation ID" column, and without that
>>>>> how would you know trace entries are in the same VP? You didn't seem
>>>>> to think an ID was needed, so you could just be confused even with
>>>>> your loop detection...)
>>>>
>>>> So in other words you still don't understand that recursive
>>>> emulation is
>>>> computationally equivalent to recursive invocation thus a detail that
>>>> can be abstracted away without effect on correct halt deciding?
>>>>
>>>> UTM1(<TM1>, DATA) ≡ TM1(DATA)
>>>> ∴
>>>> UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA))
>>>
>>> <yawn> Now you're just repeating over and over.
>>
>> OK then you both understand and agree that I am correct about this.
>>
> When someone disagrees with you, and you simply repeat yourself again,
> then you can safely assume they still disagree with you.
>
> <.. snip more repetitions of "I'm right, you're wrong" ..>
>>
>> You claimed that my specific algorithm is incorrect
>> (here it is fully encoded)
>>
>> if (loc.Simplified_Opcode == CALL)
>> if (loc.Simplified_Opcode == traced.Simplified_Opcode)
>> if (loc.Address == traced.Address)
>> if (loc.Decode_Target == traced.Decode_Target)
>> if (Count_Conditional_Branch_Instructions == 0)
>>
>> yet could not point out any actual error. In place of reasoning all you
>> have is rhetoric.
>
> What do you expect me to do with your code? Your algorithm is claiming
> to do something that is in fact impossible - pointing out an "actual
> error" would suggest you just have a bug, and when I correct that bug
> for you it will work. Well, it won't because what is wrong is your
> underlying intuition that you can spot infinite recursive emulation with
> your TEST.
>
> Also, I explained where your "proof" went wrong, but you since you don't
> really understand what a proof should be anyway, it was a bit of a waste
> of time. Actually, I was being overly generous when I said your proof
> only worked in a single-process trace context. You had not actually
> provided a "proof" that worked even for that environment. Maybe if you
> understood how that proof worked, you might have a chance of
> understanding why it doesn't work for an emulation trace context. Or
> perhaps try to construct your own counter-example for TEST.
>
>
> Mike.
>
> yet you don't see that as an impediment against computability?
>
I already posted the complete execution trace of the details of how
Halts decides halting on H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (!Input_Halts)
HALT
else
HERE: goto HERE;
}
When Halts() always simulates its input it is obvious that
Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
decided as non halting.
Just like some people really believe that 250% of all of the beings in
the universe voted for Trump some people deny infinite recursion even
when it slaps them in the face.
--
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-30 10:36 -0500 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <Nj8xH.20993$RV.15568@fx33.iad> |
| In reply to | #26214 |
On 11/29/20 10:12 PM, olcott wrote: > > You provided no basis what-so-ever to show that my reasoning is unsound > and as of today I have fully operational code proving that it is sound. Simple proof of your unsoundness, you whole basis of your argument seems to be based on the fact that H_Hat can not use the results of your Halt Decider, thus can not be contradictory. But, by the Turing Equivalence principle (which you use as the basis to write your decider as a von Neumann machine), there WILL be a Turing Machine equivalent for your whole program which is the halt decider. Obtaining said equivalent, we can then be justified in using said equivalent to write our H_Hat and present it to your program. Because it IS a computational equivalent, it will provide tha same answer as your pogram, and thus we can give you decider a proper H_Hat that includes a proper H, that you decider needs to decider on. Your decider then has 3 choices: 1) It can fail to answer, and thus be shown to not be a Universal Halt Decider (or even a partial Halt Decider that applies to Linz) 2) It can answer non-halting, at which point we can run the H_Hat simply as a real machine (NOT in your UTM, or in your UTM if it will work as a UTM and run the Halt Decider equivalent inside it), and see that H_Hat will be halting. 3) It can anser halting, at which point we can run the H_Hat (as just above) and see that it is non-halting. In all 3 cases your decider has failed, so whatever it does, it is wrong and proved not to be a proper halt decider.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 09:55 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <U_-dnROUtvp7iFjCnZ2dnUU7-eHNnZ2d@giganews.com> |
| In reply to | #26219 |
On 11/30/2020 9:36 AM, Richard Damon wrote:
> On 11/29/20 10:12 PM, olcott wrote:
>>
>> You provided no basis what-so-ever to show that my reasoning is unsound
>> and as of today I have fully operational code proving that it is sound.
>
> Simple proof of your unsoundness, you whole basis of your argument seems
> to be based on the fact that H_Hat can not use the results of your Halt
> Decider, thus can not be contradictory.
>
> But, by the Turing Equivalence principle (which you use as the basis to
> write your decider as a von Neumann machine), there WILL be a Turing
> Machine equivalent for your whole program which is the halt decider.
> Obtaining said equivalent, we can then be justified in using said
> equivalent to write our H_Hat and present it to your program. Because it
> IS a computational equivalent, it will provide tha same answer as your
> pogram, and thus we can give you decider a proper H_Hat that includes a
> proper H, that you decider needs to decider on.
>
> Your decider then has 3 choices:
>
> 1) It can fail to answer, and thus be shown to not be a Universal Halt
> Decider (or even a partial Halt Decider that applies to Linz)
>
> 2) It can answer non-halting, at which point we can run the H_Hat simply
> as a real machine (NOT in your UTM, or in your UTM if it will work as a
> UTM and run the Halt Decider equivalent inside it), and see that H_Hat
> will be halting.
>
> 3) It can anser halting, at which point we can run the H_Hat (as just
> above) and see that it is non-halting.
>
> In all 3 cases your decider has failed, so whatever it does, it is wrong
> and proved not to be a proper halt decider.
>
The x86 version of my halt deciding system currently simply aborts the
execution of main() and decides not halting if there is any code called
by main() that specifies infinite execution.
It points out the exact point in the execution trace where infinite
execution was decided. This point can be mapped back to the disassembled
source code functions.
It returns the result to the user of the halt decider.
Actual debug trace of Halts() deciding halting on main()
int main()
{
HERE:
u32 X = 5;
u32 Y = 3;
u32 Z = 0;
Z = X + Y;
goto HERE;
HALT;
}
_main()
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](03) 83ec0c sub esp,+0c
[000005ba](07) c745fc05000000 mov [ebp-04],00000005
[000005c1](07) c745f803000000 mov [ebp-08],00000003
[000005c8](07) c745f400000000 mov [ebp-0c],00000000
[000005cf](03) 8b45fc mov eax,[ebp-04]
[000005d2](03) 0345f8 add eax,[ebp-08]
[000005d5](03) 8945f4 mov [ebp-0c],eax
[000005d8](02) ebe0 jmp 000005ba
[000005da](01) f4 hlt
[000005db](02) 8be5 mov esp,ebp
[000005dd](01) 5d pop ebp
[000005de](01) c3 ret
Halt_Decider_Trace() [00010bc8] size(36) capacity(65536)
---Halt_Decider_Trace[00010be8][000005d5] NONE
---Halt_Decider_Trace[00010be4][000005d2] NONE
---Halt_Decider_Trace[00010be0][000005cf] NONE
---Halt_Decider_Trace[00010bdc][000005c8] NONE
---Halt_Decider_Trace[00010bd8][000005c1] NONE
---Halt_Decider_Trace[00010bd4][000005ba] NONE
Output_Debug_Trace() [00010bc8] size(36) capacity(65536)
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](03) 83ec0c sub esp,+0c
[000005ba](07) c745fc05000000 mov [ebp-04],00000005
[000005c1](07) c745f803000000 mov [ebp-08],00000003
[000005c8](07) c745f400000000 mov [ebp-0c],00000000
[000005cf](03) 8b45fc mov eax,[ebp-04]
[000005d2](03) 0345f8 add eax,[ebp-08]
[000005d5](03) 8945f4 mov [ebp-0c],eax
[000005d8](02) ebe0 jmp 000005ba ---- JMP [000005ba]
The PRIOR Instruction Specifies an Infinite Loop: Simulation Stopped:
Number of Instructions Executed(10)
--
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-30 12:56 -0500 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <pnaxH.49574$kM7.37472@fx43.iad> |
| In reply to | #26220 |
On 11/30/20 10:55 AM, olcott wrote: > On 11/30/2020 9:36 AM, Richard Damon wrote: >> On 11/29/20 10:12 PM, olcott wrote: >>> >>> You provided no basis what-so-ever to show that my reasoning is unsound >>> and as of today I have fully operational code proving that it is sound. >> >> Simple proof of your unsoundness, you whole basis of your argument seems >> to be based on the fact that H_Hat can not use the results of your Halt >> Decider, thus can not be contradictory. >> >> But, by the Turing Equivalence principle (which you use as the basis to >> write your decider as a von Neumann machine), there WILL be a Turing >> Machine equivalent for your whole program which is the halt decider. >> Obtaining said equivalent, we can then be justified in using said >> equivalent to write our H_Hat and present it to your program. Because it >> IS a computational equivalent, it will provide tha same answer as your >> pogram, and thus we can give you decider a proper H_Hat that includes a >> proper H, that you decider needs to decider on. >> >> Your decider then has 3 choices: >> >> 1) It can fail to answer, and thus be shown to not be a Universal Halt >> Decider (or even a partial Halt Decider that applies to Linz) >> >> 2) It can answer non-halting, at which point we can run the H_Hat simply >> as a real machine (NOT in your UTM, or in your UTM if it will work as a >> UTM and run the Halt Decider equivalent inside it), and see that H_Hat >> will be halting. >> >> 3) It can anser halting, at which point we can run the H_Hat (as just >> above) and see that it is non-halting. >> >> In all 3 cases your decider has failed, so whatever it does, it is wrong >> and proved not to be a proper halt decider. >> > > The x86 version of my halt deciding system currently simply aborts the > execution of main() and decides not halting if there is any code called > by main() that specifies infinite execution. > > It points out the exact point in the execution trace where infinite > execution was decided. This point can be mapped back to the disassembled > source code functions. > > It returns the result to the user of the halt decider. > > And you are missing the key point. I can take your code, and make the equivalent computation that returns the result to the caller. This is allowed by the computation equivalency principle, and thus your code is still subject to the Linz paradox. You do have the choice to fail to process that code, but that means you are no longer 'universal' or even partial to Linz. Yes, you can say you have define that you aren't going to handle the recurcive call case (you still won't succeed) but that automatically put you outside the classical halt problem, which specifally says ALL programs/machines.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 12:10 -0600 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <6q-dnYl4BdzzqFjCnZ2dnUU7-WHNnZ2d@giganews.com> |
| In reply to | #26223 |
On 11/30/2020 11:56 AM, Richard Damon wrote:
> On 11/30/20 10:55 AM, olcott wrote:
>> On 11/30/2020 9:36 AM, Richard Damon wrote:
>>> On 11/29/20 10:12 PM, olcott wrote:
>>>>
>>>> You provided no basis what-so-ever to show that my reasoning is unsound
>>>> and as of today I have fully operational code proving that it is sound.
>>>
>>> Simple proof of your unsoundness, you whole basis of your argument seems
>>> to be based on the fact that H_Hat can not use the results of your Halt
>>> Decider, thus can not be contradictory.
>>>
>>> But, by the Turing Equivalence principle (which you use as the basis to
>>> write your decider as a von Neumann machine), there WILL be a Turing
>>> Machine equivalent for your whole program which is the halt decider.
>>> Obtaining said equivalent, we can then be justified in using said
>>> equivalent to write our H_Hat and present it to your program. Because it
>>> IS a computational equivalent, it will provide tha same answer as your
>>> pogram, and thus we can give you decider a proper H_Hat that includes a
>>> proper H, that you decider needs to decider on.
>>>
>>> Your decider then has 3 choices:
>>>
>>> 1) It can fail to answer, and thus be shown to not be a Universal Halt
>>> Decider (or even a partial Halt Decider that applies to Linz)
>>>
>>> 2) It can answer non-halting, at which point we can run the H_Hat simply
>>> as a real machine (NOT in your UTM, or in your UTM if it will work as a
>>> UTM and run the Halt Decider equivalent inside it), and see that H_Hat
>>> will be halting.
>>>
>>> 3) It can anser halting, at which point we can run the H_Hat (as just
>>> above) and see that it is non-halting.
>>>
>>> In all 3 cases your decider has failed, so whatever it does, it is wrong
>>> and proved not to be a proper halt decider.
>>>
>>
>> The x86 version of my halt deciding system currently simply aborts the
>> execution of main() and decides not halting if there is any code called
>> by main() that specifies infinite execution.
>>
>> It points out the exact point in the execution trace where infinite
>> execution was decided. This point can be mapped back to the disassembled
>> source code functions.
>>
>> It returns the result to the user of the halt decider.
>>
>>
>
> And you are missing the key point. I can take your code, and make the
> equivalent computation that returns the result to the caller. This is
> allowed by the computation equivalency principle, and thus your code is
The halt decider is directly integrated into the emulator now so it
always makes its halting decision assuming that main() is its input. It
also proves that its halting decision is correct with the complete
exucution trace that lead to this decision.
01 int main()
02 {
03 HERE:
04 u32 X = 5;
05 u32 Y = 3;
06 u32 Z = 0;
07 Z = X + Y;
08 goto HERE;
09 HALT;
10 }
The simulation of main() is terminated at its line 08.
> still subject to the Linz paradox. You do have the choice to fail to
> process that code, but that means you are no longer 'universal' or even
> partial to Linz. Yes, you can say you have define that you aren't going
> to handle the recurcive call case (you still won't succeed) but that
> automatically put you outside the classical halt problem, which
> specifally says ALL programs/machines.
>
--
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-30 15:34 -0500 |
| Subject | Re: It is known that a correct halt decider must return false (in this case)[V4](recursive emulation ≡ recursive invocation) |
| Message-ID | <rHcxH.49580$kM7.2296@fx43.iad> |
| In reply to | #26224 |
On 11/30/20 1:10 PM, olcott wrote:
> On 11/30/2020 11:56 AM, Richard Damon wrote:
>> On 11/30/20 10:55 AM, olcott wrote:
>>> On 11/30/2020 9:36 AM, Richard Damon wrote:
>>>> On 11/29/20 10:12 PM, olcott wrote:
>>>>>
>>>>> You provided no basis what-so-ever to show that my reasoning is
>>>>> unsound
>>>>> and as of today I have fully operational code proving that it is
>>>>> sound.
>>>>
>>>> Simple proof of your unsoundness, you whole basis of your argument
>>>> seems
>>>> to be based on the fact that H_Hat can not use the results of your Halt
>>>> Decider, thus can not be contradictory.
>>>>
>>>> But, by the Turing Equivalence principle (which you use as the basis to
>>>> write your decider as a von Neumann machine), there WILL be a Turing
>>>> Machine equivalent for your whole program which is the halt decider.
>>>> Obtaining said equivalent, we can then be justified in using said
>>>> equivalent to write our H_Hat and present it to your program.
>>>> Because it
>>>> IS a computational equivalent, it will provide tha same answer as your
>>>> pogram, and thus we can give you decider a proper H_Hat that includes a
>>>> proper H, that you decider needs to decider on.
>>>>
>>>> Your decider then has 3 choices:
>>>>
>>>> 1) It can fail to answer, and thus be shown to not be a Universal Halt
>>>> Decider (or even a partial Halt Decider that applies to Linz)
>>>>
>>>> 2) It can answer non-halting, at which point we can run the H_Hat
>>>> simply
>>>> as a real machine (NOT in your UTM, or in your UTM if it will work as a
>>>> UTM and run the Halt Decider equivalent inside it), and see that H_Hat
>>>> will be halting.
>>>>
>>>> 3) It can anser halting, at which point we can run the H_Hat (as just
>>>> above) and see that it is non-halting.
>>>>
>>>> In all 3 cases your decider has failed, so whatever it does, it is
>>>> wrong
>>>> and proved not to be a proper halt decider.
>>>>
>>>
>>> The x86 version of my halt deciding system currently simply aborts the
>>> execution of main() and decides not halting if there is any code called
>>> by main() that specifies infinite execution.
>>>
>>> It points out the exact point in the execution trace where infinite
>>> execution was decided. This point can be mapped back to the disassembled
>>> source code functions.
>>>
>>> It returns the result to the user of the halt decider.
>>>
>>>
>>
>> And you are missing the key point. I can take your code, and make the
>> equivalent computation that returns the result to the caller. This is
>> allowed by the computation equivalency principle, and thus your code is
>
> The halt decider is directly integrated into the emulator now so it
> always makes its halting decision assuming that main() is its input. It
> also proves that its halting decision is correct with the complete
> exucution trace that lead to this decision.
>
>
> 01 int main()
> 02 {
> 03 HERE:
> 04 u32 X = 5;
> 05 u32 Y = 3;
> 06 u32 Z = 0;
> 07 Z = X + Y;
> 08 goto HERE;
> 09 HALT;
> 10 }
>
> The simulation of main() is terminated at its line 08.
>
You are still missing it. By DEFINITION, I can take the SOURCE CODE of
your program, and use it to make my program to submit to it. In doing
this, I can extract the answer and use in my H_Hat. You can't avoid
this. If you reject the program you fail to be universal, if you answer
you are wrong.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2020-11-24 03:53 +0000 |
| Message-ID | <87im9vpg0e.fsf@bsb.me.uk> |
| In reply to | #25761 |
olcott <NoOne@NoWhere.com> writes: > 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. Gosh. Is that a lie, or is that just very, very stupid? Lying or dumb, dumb or lying? I can never quite tell. Having only the code that loops around the single stepping DebugTrace() (presumably a simple modification to someone else's emulator) is exactly the wrong basis for a halt decider. Its the version that makes the "Hat" computation non-finite BY NOT BEING A DECIDER. The "HAT" computation you are analysing is irrelevant because it's not built on a finite decider. Only when you add the impossible "abort if needed" code would you have anything that even resembles a decider. But it's not a halt decider, because that code has ITS OWN "HAT" computation which it decides incorrectly. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-23 23:29 -0600 |
| Message-ID | <qoGdnW1Lz5qmByHCnZ2dnUU7-UPNnZ2d@giganews.com> |
| In reply to | #25781 |
On 11/23/2020 9:53 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> 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. > > Gosh. Is that a lie, or is that just very, very stupid? Lying or dumb, > dumb or lying? I can never quite tell. > > Having only the code that loops around the single stepping DebugTrace() > (presumably a simple modification to someone else's emulator) is exactly > the wrong basis for a halt decider. Its the version that makes the > "Hat" computation non-finite BY NOT BEING A DECIDER. The "HAT" > computation you are analysing is irrelevant because it's not built on a > finite decider. > > Only when you add the impossible "abort if needed" code would you have > anything that even resembles a decider. But it's not a halt decider, > because that code has ITS OWN "HAT" computation which it decides > incorrectly. > No it does not and you know that it does not. It neither has its own H_Hat computation and the one H_Hat that exists is decided correctly and you know that it is decided correctly. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2020-11-24 15:53 +0000 |
| Message-ID | <87sg8yah0c.fsf@bsb.me.uk> |
| In reply to | #25789 |
olcott <NoOne@NoWhere.com> writes: > On 11/23/2020 9:53 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> 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. >> >> Gosh. Is that a lie, or is that just very, very stupid? Lying or dumb, >> dumb or lying? I can never quite tell. >> >> Having only the code that loops around the single stepping DebugTrace() >> (presumably a simple modification to someone else's emulator) is exactly >> the wrong basis for a halt decider. Its the version that makes the >> "Hat" computation non-finite BY NOT BEING A DECIDER. The "HAT" >> computation you are analysing is irrelevant because it's not built on a >> finite decider. >> >> Only when you add the impossible "abort if needed" code would you have >> anything that even resembles a decider. But it's not a halt decider, >> because that code has ITS OWN "HAT" computation which it decides >> incorrectly. > > No it does not and you know that it does not. If you dare post the code, I'll show you, explicitly (again). > It neither has its own H_Hat computation and the one H_Hat that exists > is decided correctly and you know that it is decided correctly. Of course it has it's own -- you don't get to say I can't write one if I want. Your ruse -- to use one H_Hat and two different called functions is simply dishonest. You know about it now, but you keep pushing it because you have nothing else. Twenty years and this is all you have. Any time you fancy posting what you think is a halt decider (even if it refers to impossible-to-write code like your "needs_to_be_aborted" function), I will post the confounding example. You dare not even try because you know I'm right. Need we add intellectual cowardice to your character traits? -- Ben.
[toc] | [prev] | [next] | [standalone]
Page 8 of 11 — ← Prev page 1 … 6 7 [8] 9 10 11 Next page →
Back to top | Article view | comp.theory
csiph-web