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

Groups > comp.lang.c > #73074

Re: Is the C preprocessor turing-complete?

Show all headers | View raw

supercat@casperkitty.com writes:

> On Friday, October 16, 2015 at 11:13:25 AM UTC-5, Martin Shobe wrote:
>> > 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.
>
> Some function f(N) whose value depends sole upon N.

Ah, I wondered that too.

>> 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.
>
> Some definitions of a Turing machine specify that moving past the left
> edge is forbidden; the set of programs that are computable with a single-
> or double-ended tape are equivalent.
>
> As for your program, if the tape extends to the left of the starting point,
> any time the machine enters state 1, all of the locations that are ever
> going to be visited will be blank.

I don't think so.  The tape/state pairs are

  1, [ ]
  2, [1]
  2, [ ]1
  1, [1]
  1, 1[ ]
  2, 1[1]
  2, [1]1
  2, [ ]11
  1, [1]1
  1, 1[1]
  1, 11[ ]
  2, 11[1]

and so on.  At every point the locations that are going to be visited
will be mixture of blank and non-blank symbols (specifically a sequence
of consecutive '1' squares followed by a visit to a single blank).

> If the tape were looped through a
> scrubber, so that locations which passed out once side of the reader would
> be cleared and presented to the other side, your program would be unaffected
> even if the loop were nothing more than a single location.

I don't see how this answers Martin's question.

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