3 ms·

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 afte

by triska 8y ago

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.

kazinator 8y ago
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.
- triska 8y ago
  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.
  - kazinator 8y ago
    > 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.

by triska 8y ago

kazinator 8y ago

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.

triska 8y ago
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.
- kazinator 8y ago
  > 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.