Hacker News Reader

Comment by AnthonyMouse | Hacker News Reader

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.

View on HN

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

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.

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

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

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?

"What do you suppose happens if a Turing machine reads from a location on the tape that has never been written?"

It reads the default symbol (see e.g. the description of a TM on Wikipedia). It's semantics are well-defined.

The semantics of TMs are well-defined. The semantics of C's "undefined behavior" is not well-defined.

I should have said "blank symbol" not "default symbol".

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

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.

Clarification: all Turing complete languages allow you to do any _computation_ all Turing complete languages allow you to do.

Reply on news.ycombinator.com