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

Groups > comp.lang.c > #73042

Re: Is the C preprocessor turing-complete?

Show all headers | View raw

On 10/16/2015 10:43 AM, supercat@casperkitty.com wrote:
> On Thursday, October 15, 2015 at 8:42:47 PM UTC-5, Les Cargill wrote:
>> 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.
>
> For any given combination number of states N, all Turing machines with that
> number of states that are started with a blank tape will do one of two
> things [note that a machine with N states, started with M symbols on the tape,
> is equivalent to a machine with N+M state started with a blank tape].
>
> 1. Finish within some amount of time f(N)
>
> 2. Within that indicated amount of time achieve a scenario where its state
>     and the content of all tape locations that it will ever again examine
>     are the same as they have been previously.

"That indicated amount of time" doesn't appear to have a reference.

> Thus if the size of the Turing machine and its initial tape content are
> known there is no need for unbounded storage; there is some amount of
> storage which, if ordered in advance, will be enough.  Only one slight
> problem: f(N) grows so mind-bogglingly fast as to defy description.
> If one can imagine *any* computable function g(N) which would yield a
> finite result for arbitrary N, there will be some n0 such that for all
> N>n0, f(n0) exceeds g(n0).
>

When does the following do either 1 or 2? How large a tape do you need?

1. Is the current position blank?
1a. Yes? Write one and go to step 2.
1b. No? Move right and go to step 1.
2. Is the current position 1?
2a. Yes? Move left and go to step 2.
2b. No? Move right and go to step 1.

Martin Shobe

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