Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Equivalent halting definitions |
| Date | 2021-04-20 18:42 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20210420113133.850@kylheku.com> (permalink) |
| References | (6 earlier) <U46dnRSez7jNZ-P9nZ2dnUU7-KvNnZ2d@giganews.com> <67DfI.87002$ST2.12141@fx47.iad> <jNCdnYDTjtGwnuL9nZ2dnUU7-LnNnZ2d@giganews.com> <ezDfI.12324$v3H9.299@fx01.iad> <jcqdnRNggu4oiOL9nZ2dnUU7-XPNnZ2d@giganews.com> |
On 2021-04-20, olcott <NoOne@NoWhere.com> wrote: > On 4/20/2021 11:46 AM, Richard Damon wrote: >> Nope. Bad analogy. The second guy only has a water pistol so you don't >> need to worry about him. The X() invoked by Y() does not have the power >> to terminate the calling Y() (without breaking its contract). >> > > X() simulates Y() simulates X() > The original X() has the power to terminate Y() thus terminating the > whole call chain of Y(). If X is called with the same arguments twice, and behaves differently (for instance, on the first call it doesn't terminate, and on the second one it does) then it is not a function. One of your premises is that that X must be called twice from Y with the same arguments. That implies that X makes no decision to terminate. Whatever decision it makes has to be made on its first call, because the second call cannot turn out differently from the first call. If X stores information such as execution traces in a global variable which is shared by all invocations of X, it is not a function of its arguments. It has a hidden argument: the global state containing those traces. That violates the rule that X is called twice with the same arguments. It's called twice with only the same formal arguments declared in its procedure header, but the hidden ad-hoc argument that is the global state is changing. Functions are Turing-complete. Everything result we can prove about computability using recursive functions holds for Turing machines, and holds for imperative procedures also. It is completely general. We can use functions to analyze any situation involving imperative procedures. We just have to convert their computation into functions. The proof you're trying to dispute works with recursive functions. You must follow its conditions and use functions. You must have a rule (0) which says: X() and Y() are functions of their formal arguments, and nothing else; X() and Y() are not "functions" in the sense of "C language function", which refers to an imperative procedure. When you add that rule, it's clear that X() cannot be called twice with the same arguments, such that it makes a different decision on the second call. Thus the conclusion is that there is runaway recursion; there is no possibility of anything else as long as the "X called twice" premise is asserted. -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-19 23:20 -0500
Re: Equivalent halting definitions "dklei...@gmail.com" <dkleinecke@gmail.com> - 2021-04-19 22:21 -0700
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:26 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 11:33 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:40 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 11:52 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:59 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 12:16 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 11:37 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 12:46 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 12:56 -0500
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 18:42 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 14:28 -0500
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 20:23 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 15:34 -0500
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 22:12 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 17:24 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 14:54 -0400
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 08:04 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:33 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 11:54 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 11:03 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 12:18 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 11:38 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 12:48 -0400
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 12:44 -0500
Re: Equivalent halting definitions (identical set) Richard Damon <Richard@Damon-Family.org> - 2021-04-20 14:57 -0400
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 14:23 -0500
Re: Equivalent halting definitions (identical set) Richard Damon <Richard@Damon-Family.org> - 2021-04-20 16:32 -0400
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 15:54 -0500
Re: Equivalent halting definitions (identical set) André G. Isaak <agisaak@gm.invalid> - 2021-04-20 15:24 -0600
Re: Equivalent halting definitions (identical set) Richard Damon <Richard@Damon-Family.org> - 2021-04-20 17:31 -0400
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 17:02 -0500
Re: Equivalent halting definitions (identical set) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 22:09 +0000
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 19:03 -0500
Re: Equivalent halting definitions (identical set) Richard Damon <Richard@Damon-Family.org> - 2021-04-20 21:52 -0400
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 21:57 -0500
Re: Equivalent halting definitions (identical set) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-21 04:27 +0100
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-20 22:40 -0500
Re: Equivalent halting definitions (identical set) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-21 14:10 +0100
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-21 09:07 -0500
Re: Equivalent halting definitions (identical set) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-21 23:54 +0100
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-21 18:48 -0500
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-21 19:06 -0500
Re: Equivalent halting definitions (identical set) Richard Damon <Richard@Damon-Family.org> - 2021-04-21 07:59 -0400
Re: Equivalent halting definitions (identical set) olcott <NoOne@NoWhere.com> - 2021-04-21 09:10 -0500
Re: Equivalent halting definitions (identical set) Richard Damon <Richard@Damon-Family.org> - 2021-04-21 11:24 -0400
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 08:27 -0400
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 15:18 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:28 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 11:34 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:41 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 11:57 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 11:10 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 12:22 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 11:42 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 14:58 -0400
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 16:51 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 12:02 -0500
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 18:46 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 14:20 -0500
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 20:24 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 15:36 -0500
Re: Equivalent halting definitions Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-20 22:13 +0000
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 17:25 -0500
Re: Equivalent halting definitions Richard Damon <Richard@Damon-Family.org> - 2021-04-20 15:00 -0400
Re: Equivalent halting definitions olcott <NoOne@NoWhere.com> - 2021-04-20 10:29 -0500
csiph-web