From owner-sc22wg14+sc22wg14-domo2=www.open-std.org@open-std.org Thu Sep 27 17:24:15 2012 Return-Path: X-Original-To: sc22wg14-domo2 Delivered-To: sc22wg14-domo2@www.open-std.org Received: by www.open-std.org (Postfix, from userid 521) id 6F134356925; Thu, 27 Sep 2012 17:24:15 +0200 (CEST) Delivered-To: sc22wg14@open-std.org Received: from outbound-queue-2.mail.thdo.gradwell.net (outbound-queue-2.mail.thdo.gradwell.net [212.11.70.35]) by www.open-std.org (Postfix) with ESMTP id 33A7C356925 for ; Thu, 27 Sep 2012 17:24:14 +0200 (CEST) Received: from outbound-edge-1.mail.thdo.gradwell.net (bonnie.gradwell.net [212.11.70.2]) by outbound-queue-2.mail.thdo.gradwell.net (Postfix) with ESMTP id 629E322704; Thu, 27 Sep 2012 16:24:13 +0100 (BST) Received: from digraph.polyomino.org.uk (HELO digraph.polyomino.org.uk) (81.187.227.50) (smtp-auth username postmaster%pop3.polyomino.org.uk, mechanism cram-md5) by outbound-edge-1.mail.thdo.gradwell.net (qpsmtpd/0.83) with (AES256-SHA encrypted) ESMTPSA; Thu, 27 Sep 2012 16:24:13 +0100 Received: from jsm28 (helo=localhost) by digraph.polyomino.org.uk with local-esmtp (Exim 4.76) (envelope-from ) id 1THFwi-0005tH-Ec; Thu, 27 Sep 2012 15:24:12 +0000 Date: Thu, 27 Sep 2012 15:24:12 +0000 (UTC) From: "Joseph S. Myers" X-X-Sender: jsm28@digraph.polyomino.org.uk To: sc22wg14@open-std.org cc: mail@robbertkrebbers.nl, freek@cs.ru.nl Subject: N1637 and the Turing-completeness of C Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Gradwell-MongoId: 50646f9d.83e1-4929-1 X-Gradwell-Auth-Method: mailbox X-Gradwell-Auth-Credentials: postmaster@pop3.polyomino.org.uk Sender: owner-sc22wg14@open-std.org Precedence: bulk N1637 provides an argument that C does not admit Turing-complete implementations without I/O - that programs without I/O correspond to finite state machines and so have decidable termination. With the inclusion of threads in C11, I think this needs a further qualification that it is considering only single-threaded C programs. Certainly the argument about bounds on recursion is assuming a single flow of control. Furthermore, it seems to me that given two threads, an infinite tape can be implemented through recursion; the stack of one thread contains the non-blank parts of the tape to the left of the currently active position, and the stack of the other thread contains the non-blank parts of the tape to the right of the currently active position, and each thread either recurses or returns from a recursive function as appropriate depending on the direction of motion (a third thread can actually run the Turing machine, successively pushing newly written values on one side of the tape and reading values from the other, though probably you don't actually need a third thread). Now, some people have argued that all objects have addresses - that even if their address is never taken, and even if they have the register storage class, they must still have addresses somewhere in the address space. N1637 does not seem to refer to this argument. But even if it is supposed to be true, it does not affect the above construction for a Turing machine using two threads. While objects with automatic storage duration would, under this argument, need to have distinct addresses, no such objects are actually needed to store the tape. You can store a number in the size of a VLA typedef, and while in implementation terms that size is much like an object with automatic storage duration, nothing makes it an object in C standard terms. So the recursive function can return void, have no parameters, and have no automatic variables, along the lines of: volatile _Atomic size_t v; /* Variable for communication between threads. */ void recurse (void) { typedef char T[atomic_load (&v)]; /* Signal that push of v onto tape is complete. */ for (;;) { /* Wait for signal of whether to push or pop this side of the tape. */ if (push requested) recurse (); else { atomic_store (&v, sizeof (T)); /* Signal that popped value is available in v. */ return; } } } Thus threads may have added Turing-completeness to no-I/O C programs in C11 where C99 did not have such Turing-completeness. -- Joseph S. Myers joseph@codesourcery.com