jessicat comments on Second-Order Logic: The Controversy - Less Wrong

24 Post author: Eliezer_Yudkowsky 04 January 2013 07:51PM

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

Article Navigation

Comments (188)
Tags: seq_epistemology meaning numbers logic proofs math

Comments (188)

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

Comment author: jessicat 07 April 2015 10:17:33PM *  0 points [-]

It's possible to compute whether each machine halts using an inductive Turing machine like this:

initialize output tape to all zeros, representing the assertion that no Turing machine halts
for i = 1 to infinity
. for j = 1 to i
. . run Turing machine j for i steps
. . if it halts: set bit j in the output tape to 1

Is this what you meant? If so, I'm not sure what this has to do with observing loops.

When you say that every nonhalting Turing machine has some kind of loop, do you mean the kind of loop that many halting Turing machines also contain?

Comment author: [deleted] 19 April 2015 07:12:31PM 0 points [-]

When you say that every nonhalting Turing machine has some kind of loop, do you mean the kind of loop that many halting Turing machines also contain?

No, I mean precisely the fact that it doesn't halt. You can think of it as an infinitely growing recursion if that helps, but what's in question is really precisely the nonhalting behavior.

I'm going to make a Discussion post about the matter, since Luke wants me to share the whole informal shpiel on the subject.

Powered by Reddit Powered by Reddit