Groups | Search | Server Info | Login | Register

Groups > comp.theory > #139304

Re: a subset of turing machines can still be turing complete

From Mikko <mikko.levanto@iki.fi>
Newsgroups comp.theory
Subject Re: a subset of turing machines can still be turing complete
Date 2026-01-21 10:45 +0200
Organization A noiseless patient Spider
Message-ID <10kq3n6$1vb0d$1@dont-email.me> (permalink)
References <10kpfrd$1o0br$6@dont-email.me>

Show all headers | View raw

On 21/01/2026 05:06, dart200 wrote:
> for example:
> 
> the subset of all turing machines that do not take input is in fact a 
> turing-complete set of machines, in that it can express all computation 
> that is possible by turing macines,

That's right. A computation that takes some input can be computed with
a machine that first writes the inpt to the tape and then acts linke
a machine that performs the computation for that tape content as input.

However, if you want the ability to computate different computations
with the same machine you do need a machine that takes an input.

> therefore we do not need all possible turing machines, in our set of 
> machines, to produce a turing-complete set of machines

No, but we may need them for other purposes.

-- 
Mikko

Back to comp.theory | Previous | Next — Previous in thread | Find similar

Thread

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