Groups | Search | Server Info | Login | Register

Groups > comp.theory > #139295

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

Show all headers | View raw

On 1/20/26 10:06 PM, 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,
> 
> therefore we do not need all possible turing machines, in our set of 
> machines, to produce a turing-complete set of machines
> 
> anyone care to disagree?
> 



Nothing says that you need "All Turing Machines" to have a Turing 
Complete set of machines, as a given Computation can be inplmented with 
an infinite number of different machines (one of the reasons you can't 
detect that your input contains a copy of yourself.) It does say that 
your set of machines needs to include within its set, machines with the 
sub-machines containing at least one verion of the countably infinite 
number of Turing Machine implementations of the Countably infinite set 
for Turing Machine Computable computations.

Your collection WILL need to have each of these having a clear break in 
them between the "generation" of the effective input and the sub-machine 
that performs the computation (though this might not be actually 
detectible in the actual code), so you DO have an algorithm that 
performs the compuation, and that sub-machine is what you will copy when 
you build a copy of the algorithm. Remember, a clearly defined algorith 
which is applied to an input is part of the definition.

And it is a fact that your reflection trick still doesn't let your 
decider detect that the input is a pathological usage of itself, as the 
representation of itself can easily use a encoding of itself that is 
different than what the reflect command generates, using a different 
representaiton of the decider than what the decider checks for.

Remember, the pathological program provides the decider with *A* 
representation of itself, there is no limitation on how this is made, in 
particular, it doesn't need to match the machine description your 
REFLECT command generates (which you still need to define HOW it does 
that). Thus, the decider can't tell that the input it got actually 
represents the program it is part of,

Back to comp.theory | Previous | Next — Previous in thread | Next 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