Groups | Search | Server Info | Login | Register
Groups > comp.theory > #139333
| From | dart200 <user7160@newsgrouper.org.invalid> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: a subset of turing machines can still be turing complete |
| Date | 2026-01-22 15:21 -0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <10kube0$3ci1e$1@dont-email.me> (permalink) |
| References | <10kpfrd$1o0br$6@dont-email.me> <FXXbR.239463$VY9.52946@fx10.iad> <10kqve0$28eco$1@dont-email.me> <10krt4d$2jek9$1@dont-email.me> |
On 1/21/26 5:05 PM, Tristan Wibberley wrote:
> On 21/01/2026 16:38, dart200 wrote:
>> a current thesis of mine is that given a total enumeration of TM (in
>> order of increasing complexity/number of states), no paradoxical machine
>> produces an input->output mapping that is a first of it's kind - ie
>> there will always be some simpler machine that exists and produces an
>> equivalent input->output mapping.
>
> Just for clarity, do you mean to say that for every tuple of tuples
> {initial states {tape×machine} × final states {tape×machine}} there is a
> halting machine that has fewer states than any non-halting machine?
>
> Yes, because none of the nonhalting machines has a final state so its
> tuple can't be constructed and therefore is not first of anything, and
> is /not/, just /isn't/.
>
> Do you mean there is a simpler machine with the same initial state for
> each of the nonhalting machine's reachable states?
>
let us refer to turing's solution for defining "output" in regards to
infinitely running machines, because they can still have output:
the tape is divided into alternating cells: F-squares (figure) and
E-squares (erasure). F-squares hold permanent output of the computed
sequence, and can only be written once. E-squares are for
temporary/scratch work necessary for the computation, but not actually
the output of the machine.
in fact this works for all machines halting and non-halting: all output
will reside in the F-squares, where as all temp non-output work is done
in E-squares. so now not only can we differentiate output between
halting machines, we can also differentiate output for machines that are
infinitely running (which was important for turing's proof!).
this ofc is just a convention coded into the machine_description, but
the set of machines following that convention is just as turing-complete
as the ones not following that convention. modern programing languages
don't really encapsulate such conventions because output is synonymous
with halting functions, and infinitely running functions are used for
things that do not have output like ui or event loops.
so considering such a paradigm what i'm saying: all the paradox
non-sense happens in the E-square space, and ultimately only selects an
execution path, and that path is what defines the output written to
F-squares. but that execution path can exist simply without all the
paradox nonsense, just as well. so therefore for any machine containing
a paradox, there is a simpler, yet functionally equivalent machine that
does not.
--
arising us out of the computing dark ages,
please excuse my pseudo-pyscript,
~ nick
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar
a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-20 19:06 -0800
Re: a subset of turing machines can still be turing complete Richard Damon <Richard@Damon-Family.org> - 2026-01-20 22:43 -0500
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-21 08:38 -0800
Re: a subset of turing machines can still be turing complete Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-22 01:05 +0000
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-22 15:21 -0800
Re: a subset of turing machines can still be turing complete Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-22 23:56 +0000
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-22 21:51 -0800
Re: a subset of turing machines can still be turing complete Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-23 11:53 -0500
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-23 10:30 -0800
Re: a subset of turing machines can still be turing complete Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-23 17:59 -0500
Re: a subset of turing machines can still be turing complete Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-28 23:22 +0000
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-29 21:18 -0800
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-22 17:58 -0600
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-22 21:21 -0800
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-23 04:19 -0600
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-23 08:29 -0800
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-23 11:14 -0600
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-23 11:24 -0600
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-23 18:01 -0500
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-23 17:50 -0600
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-23 20:30 -0500
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-23 19:51 -0600
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-23 20:56 -0500
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-23 21:05 -0600
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-24 07:16 -0500
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-24 08:21 -0600
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-24 09:39 -0500
Re: a subset of Turing machines can still be Turing complete PLO olcott <polcott333@gmail.com> - 2026-01-24 09:48 -0600
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-24 12:19 -0500
Re: a subset of Turing machines can still be Turing complete PLO Mikko <mikko.levanto@iki.fi> - 2026-01-24 10:42 +0200
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 01:21 -0800
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-24 07:24 -0500
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 08:49 -0800
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-24 12:24 -0500
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 14:28 -0800
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-24 19:52 -0500
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-24 19:03 -0800
Re: a subset of Turing machines can still be Turing complete PLO Richard Damon <Richard@Damon-Family.org> - 2026-01-25 13:20 -0500
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-25 13:07 -0800
Re: a subset of Turing machines can still be Turing complete PLO Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-01-29 00:15 +0000
Re: a subset of Turing machines can still be Turing complete PLO dart200 <user7160@newsgrouper.org.invalid> - 2026-01-29 00:28 -0800
Re: a subset of Turing machines can still be Turing complete PLO Mikko <mikko.levanto@iki.fi> - 2026-01-25 13:12 +0200
Re: a subset of turing machines can still be turing complete Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-21 22:41 -0500
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-22 21:44 -0800
Re: a subset of turing machines can still be turing complete Richard Damon <Richard@Damon-Family.org> - 2026-01-23 11:59 -0500
Re: a subset of turing machines can still be turing complete dart200 <user7160@newsgrouper.org.invalid> - 2026-01-23 10:42 -0800
Re: a subset of turing machines can still be turing complete Richard Damon <news.x.richarddamon@xoxy.net> - 2026-01-23 17:45 -0500
Re: a subset of turing machines can still be turing complete Mikko <mikko.levanto@iki.fi> - 2026-01-21 10:45 +0200
csiph-web