Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

This is all true, and a good summary of the situation. These points are also explained in more detail in the post I linked to.

If we use streams as an oracle, then we can represent an unbounded tape, and C together with such streams let us model any Turing machine. However, this is not sufficient to prove that C is Turing-complete: To show that (in this context), one has to express also the semantics of such streams within C! It is at this point that the mentioned limitation manifests itself with this approach.



How is it not within C? FILE * Streams are defined by the C language. When you write a byte into a file, and there is no external meddling, you can read the same byte back. A stream is just a language-defined dynamic data structure which retains the last value that was stored into it, like a list or hash table.

C also has declarations and for loops. If you use them to build your Universal Turing Machine, why doesn't the same objection apply to those features? I mean: "but you're not expressing declarations or for loops in C, you're just invoking these ready-made feature by their convenient, ready-made syntax!"


These are all good points. However, there are now assumptions that do not follow from the C standard, such that you can read the same byte back from a file after writing it. As the post I linked to mentions, you can indeed model an unbounded tape if you assume the existence of streams with such strong properties and rely on their semantics in your solution.

This assumes facilities that are not prescribed by the C standard though, such as a data structure whose semantics cannot be expressed in C in general. This is a rather striking difference to other constructs such as declarations and for loops: If pressed, we could express their semantics within C while relying exclusively on features that are prescribed by the standard.


C99, 7.19.2 Streams, ¶3: Data read in from a binary stream shall compare equal to the data that were earlier written out to that stream, under the same implementation. Such a stream may, however, have an implementation-defined number of null characters appended to the end of the stream.


Again a very good point! The key assumption that breaks down in general, that is, unless you assume an unbounded storage system, is that the data can be written at all. As also the post I linked to states: C together with an unbounded storage system is definitely Turing-complete!

How to specify such a system with C remains unsolved though, unless you assume its existence and availability via streams in the first place. This is in contrast to the other languages I mentioned, where you can specify the semantics of an unbounded storage system via built-in mechanisms and data structures of these languages.


> unless you assume its existence and availability via streams in the first place

That's given by a conforming, hosted implementation of ISO C (the usual kind). You seem to have been writing about freestanding implementations. We are then severely restricted; there might not be a malloc.

C99 4. Conformance ¶6: "The two forms of conforming implementation are hosted and freestanding. A conforming hosted implementation shall accept any strictly conforming program. A conforming freestanding implementation shall accept any strictly conforming program that does not use complex types and in which the use of the features specified in the library clause (clause 7) is confined to the contents of the standard headers <float.h>, <iso646.h>, <limits.h>, <stdarg.h>, <stdbool.h>, <stddef.h>, and <stdint.h>."

If we are talking hosted, then <stdio.h> streams have to be present as a required feature.

> you can specify the semantics of an unbounded storage system via built-in mechanisms and data structures of these languages.

Which language states that programs must be successfully processed by an implementation, regardless of the resources that they require? The next cons call in your Lisp image could fail. That's no different from a stream-related resource problem.

The thought experiment behind "can this programming language express Turing computation" requires us to imagine, for all languages, that the resource constraints don't exist. The question is whether there are some limitations in the language semantics which cannot be thus hand-waved away. Freestanding C (without streams) has those limitations in the abstract semantics; hosted C doesn't. The abstract semantics of streams is available, and if we imagine that to be free of platform-related resource limitation, then we are in the same league as the other languages that we have imagined to be free of platform-related resource limitations.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: