4 ms·

They come from the C language allowing it.

AnthonyMouse 13y ago
All Turing complete languages allow you to do anything all Turing complete languages allow you to do. You can allocate a huge block of memory in Java or C# and then write your own malloc to allocate buffers from subsets of it. In some cases that may have better performance. It also allows you to have buffer overruns. You can run right off the end of one buffer and into the next and the language won't stop you because it only knows that you haven't reached the end of the array it allocated.
- lomnakkus 13y ago
  Do Turing machines have a concept of "undefined behavior" in the same way that C does? AFAICT all behavior of a Turing machine is defined -- sure you might not calculate what you want, but that doesn't admit arbitrary behvaior outside of the semantics of the machine as in the C language.
  - unstabilo 13y ago
    "Undefined behavior" means "undefined by the language specification", but it is well defined by the compiler implementation. In other words, you never use the C language, always an implementation.
    - lmm 13y ago
      You're thinking of implementation-defined behaviour. Undefined behaviour is not well-defined; the compiler does not have to implement it consistently or sanely, and certainly gcc won't.
  - deleted 13y ago
    [deleted]
  - AnthonyMouse 13y ago
    > Do Turing machines have a concept of "undefined behavior" in the same way that C does? Sure they do. For example, nothing in the Turing machine specification tells you how fast they are. Whether a given program will run on a Turing machine in a given amount of wall clock time is undefined. Here's a real example with real machines. Suppose you have a program with two threads. The first thread computes data and puts it on a queue for the second thread, the second thread writes it to the filesystem. When the compute thread has computed all of the data, it sleeps for 10 seconds and then terminates the program without checking whether the write thread has actually completed writing all the data to the filesystem. That results in undefined behavior in every real language I've ever heard of. Whether the data is all written depends on how fast the CPU is, how fast the filesystem is, what other programs are scheduled on the machine that compete for CPU and filesystem access at what priority, etc. Languages don't define any of those things so you have undefined behavior.
    - dllthomas 13y ago
      That's a different abstraction than "Turing Machine". Turing machines do not have '"undefined behavior" in the same way that C does' - it would look like a "in state 3, if you read a 0, move to an arbitrary state, write arbitrary symbols to arbitrary locations on the tape, move head to an arbitrary position on the tape, and possibly restructure the state machine in arbitrary ways."
      - AnthonyMouse 13y ago
        Turing machines have undefined behavior in exactly the same way that C does. What do you suppose happens if a Turing machine reads from a location on the tape that has never been written? The value the machine observes in that circumstance is not required to be well-defined in order for the machine to be able to do all computations required of a Turing machine. Moreover, the more you add features of actual machines like parallelism and timers, the more opportunities for undefined behavior you introduce. What do you suppose a multiprocessor Turing machine does if you write concurrently to the tape without locking?
        13y ago
- ajanuary 13y ago
  Clarification: all Turing complete languages allow you to do any _computation_ all Turing complete languages allow you to do.
- dllthomas 13y ago
  "All Turing complete languages allow you to do anything all Turing complete languages allow you to do." This is false. All Turing Complete languages allow you to compute anything other Turing Complete languages allow you to compute, but that says nothing about encoding, or about interaction with the world. For an obvious encoding example, imagine you have a turning machine that can write only the symbols 0 and 2 to its tape. This is obviously Turing complete - it's isomorphic to a TM that writes 0 and 1, the TM doesn't care how the symbols are labelled. Now, if we ask it to encode 7 it has no trouble doing that in some encoding, but that can't ever be "111" on the tape.
humbledrone 13y ago
The Python language allows constructs such as socket.write(my_private_key). Do you think that just because Python makes it possible to write your private key to a socket that it must necessarily happen?

All Turing complete languages allow you to do anything all Turing complete languages allow you to do. You can allocate a huge block of memory in Java or C# and then write your own malloc to allocate buffers from subsets of it. In some cases that may have better performance. It also allows you to have buffer overruns. You can run right off the end of one buffer and into the next and the language won't stop you because it only knows that you haven't reached the end of the array it allocated.

lomnakkus 13y ago
Do Turing machines have a concept of "undefined behavior" in the same way that C does? AFAICT all behavior of a Turing machine is defined -- sure you might not calculate what you want, but that doesn't admit arbitrary behvaior outside of the semantics of the machine as in the C language.
- unstabilo 13y ago
  "Undefined behavior" means "undefined by the language specification", but it is well defined by the compiler implementation. In other words, you never use the C language, always an implementation.
  - lmm 13y ago
    You're thinking of implementation-defined behaviour. Undefined behaviour is not well-defined; the compiler does not have to implement it consistently or sanely, and certainly gcc won't.
- deleted 13y ago
  [deleted]
- AnthonyMouse 13y ago
  > Do Turing machines have a concept of "undefined behavior" in the same way that C does? Sure they do. For example, nothing in the Turing machine specification tells you how fast they are. Whether a given program will run on a Turing machine in a given amount of wall clock time is undefined. Here's a real example with real machines. Suppose you have a program with two threads. The first thread computes data and puts it on a queue for the second thread, the second thread writes it to the filesystem. When the compute thread has computed all of the data, it sleeps for 10 seconds and then terminates the program without checking whether the write thread has actually completed writing all the data to the filesystem. That results in undefined behavior in every real language I've ever heard of. Whether the data is all written depends on how fast the CPU is, how fast the filesystem is, what other programs are scheduled on the machine that compete for CPU and filesystem access at what priority, etc. Languages don't define any of those things so you have undefined behavior.
  - dllthomas 13y ago
    That's a different abstraction than "Turing Machine". Turing machines do not have '"undefined behavior" in the same way that C does' - it would look like a "in state 3, if you read a 0, move to an arbitrary state, write arbitrary symbols to arbitrary locations on the tape, move head to an arbitrary position on the tape, and possibly restructure the state machine in arbitrary ways."
    - AnthonyMouse 13y ago
      Turing machines have undefined behavior in exactly the same way that C does. What do you suppose happens if a Turing machine reads from a location on the tape that has never been written? The value the machine observes in that circumstance is not required to be well-defined in order for the machine to be able to do all computations required of a Turing machine. Moreover, the more you add features of actual machines like parallelism and timers, the more opportunities for undefined behavior you introduce. What do you suppose a multiprocessor Turing machine does if you write concurrently to the tape without locking?
      - 13y ago
ajanuary 13y ago
Clarification: all Turing complete languages allow you to do any _computation_ all Turing complete languages allow you to do.
dllthomas 13y ago
"All Turing complete languages allow you to do anything all Turing complete languages allow you to do." This is false. All Turing Complete languages allow you to compute anything other Turing Complete languages allow you to compute, but that says nothing about encoding, or about interaction with the world. For an obvious encoding example, imagine you have a turning machine that can write only the symbols 0 and 2 to its tape. This is obviously Turing complete - it's isomorphic to a TM that writes 0 and 1, the TM doesn't care how the symbols are labelled. Now, if we ask it to encode 7 it has no trouble doing that in some encoding, but that can't ever be "111" on the tape.

humbledrone 13y ago

The Python language allows constructs such as socket.write(my_private_key). Do you think that just because Python makes it possible to write your private key to a socket that it must necessarily happen?