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: Nick_Tarleton 05 January 2013 01:19:13AM 19 points [-]

I kept expecting someone to object that "this Turing machine never halts" doesn't count as a prediction, since you can never have observed it to run forever.

Comment author: [deleted] 19 March 2015 08:13:05AM *  0 points [-]

Technically speaking, you can observe the loop encoded in the Turing machine's code somewhere -- every nonhalting Turing machine has some kind of loop. The Halting theorems say that you cannot write down any finite program which will recognize and identify any infinite loop, or deductively prove the absence thereof, in bounded time. However, human beings don't have finite programs, and don't work by deduction, so I suspect, with a sketch of mathematical grounding, that these problems simply don't apply to us in the same way they apply to regular Turing machines.

EDIT: To clarify, human minds aren't "magic" or anything: the analogy between us and regular Turing machines with finite input and program tape just isn't accurate. We're a lot closer to inductive Turing machines or generalized Turing machines. We exhibit nonhalting behavior by design and have more-or-less infinite input tapes.

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