You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Viliam comments on Open Thread May 23 - May 29, 2016 - Less Wrong Discussion

4 Post author: Gunnar_Zarncke 22 May 2016 09:11PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (120)

You are viewing a single comment's thread. Show more comments above.

Comment author: Viliam 26 May 2016 08:40:52AM *  0 points [-]

Turing machines do not need memory pointers: they observe only the symbol where the reading head is.

Sure, but any system that emulates the TM and the tape would need it. (In other words, it feels like cheating to say that memory is a part of the usual computer, but tape is not a part of the TM.)

Comment author: MrMind 26 May 2016 09:20:25AM *  1 point [-]

I still don't see where the difficulty is. You need a memory registry only if you need random access to said memory, but the TM does not need it.
Sure, if you want to emulate a TM on a system that already uses random access memories, like most modern systems do, than of course you need a sufficiently long pointer for a sufficiently wide memory. But that is an accident of how systems work today, not an inherent complexity: you could easily emulate the TM in an old mainframe with a magnetic tape without ever seeing a memory pointer.