Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #73019

Re: Is the C preprocessor turing-complete?

Show all headers | View raw

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Les Cargill <lcargill99@comcast.com> writes:
>>The tape need not be ... perfectly infinite, it just needs to be long
>>enough to not run out during the operation of that particular Turing 
>>machine.
>>"Imagine if you will that Turing machines are produced with a very long 
>>but finite tape and if the machine ever runs out of space you can just 
>>order some more tape. This is the difference between the tape actually 
>>being infinitely long or just unlimited"
>
>   »Infinite« means that any operation can run on the tape,
>   whatever it's tape requirements are. When one can always
>   order more tape, than the tape /is/ /perfectly/ infinity.
>   The order process is just an implementation detail of infinity.
>   »Not infinite« means that eventually one tape order will fail.
>   And this is going to happen according to current world models.

I prefer Les Cargill's use of terms here.  I don't think there is any
disagreement about facts here, but the physical metaphor of a tape make
the use of terms like "infinite" potentially misleading.  "The tape"
refers both to what's on it (the machine's current, always finite, data)
and to the unlimited resource where future data may be put.

If, instead, we model the store of the machine as a single integer, I
think you can see that talking about this integer as "infinite" is wrong
(or at least very confusing).  It is unbounded or, to put it
differently, drawn from an infinite set.  Had the storage of a Turing
machine always been described as "a number" then nothing about it would
ever be talked about as being infinite.

Going back to tapes, your analogy of buying more is a good one, but I'd
take it further.  I'd think of the tape as always finite but when a
transition occurs, the tape is replaced by a new finite tape.  In that
picture, "the tape" is not infinite.  The only infinite thing is the set
of possible tapes.

<snip>
-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Is the C preprocessor turing-complete? Anonymous Shadow <rocket.penguin@riseup.net> - 2015-10-10 18:23 +0800
  Re: Is the C preprocessor turing-complete? Philipp Klaus Krause <pkk@spth.de> - 2015-10-10 12:33 +0200
    Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-10 13:39 -0500
      Re: Is the C preprocessor turing-complete? raltbos@xs4all.nl (Richard Bos) - 2015-10-14 11:33 +0000
        Re: Is the C preprocessor turing-complete? Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-15 10:44 -0700
          Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-15 11:34 -0700
            Re: Is the C preprocessor turing-complete? Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-16 05:17 -0700
        Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-15 20:46 -0500
          Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-15 23:21 -0500
          Re: Is the C preprocessor turing-complete? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-16 11:24 +0100
          Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-16 08:43 -0700
            Re: Is the C preprocessor turing-complete? Martin Shobe <martin.shobe@yahoo.com> - 2015-10-16 11:13 -0500
              Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-16 11:42 -0700
                Re: Is the C preprocessor turing-complete? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-16 21:48 +0100
                Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-16 14:01 -0700
  Re: Is the C preprocessor turing-complete? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-10-10 03:53 -0700
  Re: Is the C preprocessor turing-complete? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-10-10 11:59 +0000
  Re: Is the C preprocessor turing-complete? supercat@casperkitty.com - 2015-10-10 13:02 -0700
    Re: Is the C preprocessor turing-complete? Anonymous Shadow <rocket.penguin@riseup.net> - 2015-10-11 04:20 +0800
  Re: Is the C preprocessor turing-complete? Michael Barry <barrym95838@yahoo.com> - 2015-10-15 21:45 -0700
    Re: Is the C preprocessor turing-complete? James Kuyper <jameskuyper@verizon.net> - 2015-10-16 09:49 -0400
      Re: Is the C preprocessor turing-complete? Richard Heathfield <rjh@cpax.org.uk> - 2015-10-16 14:54 +0100
        Re: Is the C preprocessor turing-complete? James Kuyper <jameskuyper@verizon.net> - 2015-10-16 10:39 -0400
        Re: Is the C preprocessor turing-complete? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-16 11:25 -0400
          Re: Is the C preprocessor turing-complete? Les Cargill <lcargill99@comcast.com> - 2015-10-16 12:29 -0500
        Re: Is the C preprocessor turing-complete? Robert Wessel <robertwessel2@yahoo.com> - 2015-10-16 10:39 -0500

csiph-web