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

Groups > comp.lang.c > #73008

Re: Is the C preprocessor turing-complete?

Show all headers | View raw

Richard Bos wrote:
> Les Cargill <lcargill99@comcast.com> wrote:
>
>> Stefan Ram wrote:
>>> Philipp Klaus Krause <pkk@spth.de> writes:
>>>> You might want to have at Immanuel's winning "Best abuse of the C
>>>> preprocessor" entry in the 2001 obfuscated C contest. In particular, see
>>>> http://www.ioccc.org/2001/herrmann1.hint
>>>
>>>     Immanuel says that the reason the preprocessor is not
>>>     Turing-complete is that it has a finite number of states.
>>>     Every C program also has only a finite number of states,
>>>     since the volume of the usable universe is finite and
>>>     a state cannot occupy less volume than a Planck volume,
>>>     so C is not Turing-complete either.
>>
>> Turing machines are only potentially infinite in the time
>> dimension.
>
> Surely if you're allowed infinite time, then for certain algorithms you
> _must_ also be allowed infinite storage?
>

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…"

http://www.i-programmer.info/babbages-bag/23-turing-machines.html

Again, infinite only *over time* :)

> That said, the above is not the reason the preprocessor is
> non-Turing-complete anyway. It's non-complete simply because it doesn't
> have _any_ form of looping at all.
>
> Richard
>
-- 
Les Cargill

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