Groups | Search | Server Info | Login | Register
Groups > comp.theory > #139334
| From | Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: a subset of turing machines can still be turing complete |
| Date | 2026-01-22 23:56 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <10kudfu$3fch3$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> <10kube0$3ci1e$1@dont-email.me> |
On 22/01/2026 23:21, dart200 wrote:
> 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.
I think you need to restrict your quantification of machines called
"paradoxical" to those that only write such squares once yet have a
state whereupon that notion of output doesn't extend yet the machine
doesn't halt. Perhaps Turing defines that notion as /the/ meaning of
"paradoxical" and if so, I think it must be cited to form a useful
challenge.
I think it is an important improvement to restate your conjecture but
you should not take this message as an indication that I will reply
further - I probably will but I have other things I'm thinking about
even though I value this process greatly for combing my brain into the
mental coiffure that easily formalises conjectures and reduces them to
intuitive lemmas.
--
Tristan Wibberley
The message body is Copyright (C) 2026 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.
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