Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Non-computability.

Name: Anonymous 2010-03-04 21:21

According to Roger Penrose, humans can perform non-computable feats, such as dealing with Gödel questions. He uses this as a foundation to claim that the human mind cannot be expressed in terms of classical processes, and as such must be party to the only other (known) game in town: Quantum Mechanics.

Now, I haven't had the patience to sit through all of his arguments yet, though I slowly make progress. My understanding is that a large part of his stance is that an algorithm cannot usefully deal with a Gödel question, or equivalently, with the halting problem, while a human can.

My objection to this is that such problems always demand a certain quality of response when asked of UTMs: failing to respond forever is not acceptable as correct, nor is providing any response other than one that yields a truth when taken in combination with the question. This much is fine, however, when it is time for the human to answer, he is permitted the liberty of rejecting the question on the grounds that it is inherently unanswerable.

Obviously I am interested in artificial intelligence, and also find his assertion to be simply a self-serving one with a contrived philosophical backdrop for foundation. If anyone knows of, or can think of, a more sophisticated argument than the one above (or expose my flaws in my assessment of it) I would like to hear it.

Apologies for bringing up a largely philosophical question, my only excuse is that I cannot trust any other board with the question.

Name: Anonymous 2010-03-04 22:09

his stance is that an algorithm cannot usefully deal with a Gödel question, or equivalently, with the halting problem, while a human can.
He is an elitist and likely knows he is wrong, but is still in denial that humans are nothing more than simple biological machines following instructions. The halting problem for example, is solvable for any computer with finite resources. That is, in this universe, the halting problem is always solvable. The fact that we exist in this universe is evidence that we are not better than a machine, and in-fact, you could argue in a scenario with theoretically infinite resources a human would fail to solve the halting problem too.

Name: Anonymous 2010-03-04 22:38

>>2
The halting problem for example, is solvable for any computer with finite resources.
No, this is not correct.

Name: Anonymous 2010-03-04 22:52

>>3
Yes, yes it is.

Name: Anonymous 2010-03-04 23:07

I cannot trust any other board with the question
Your gay

Name: Anonymous 2010-03-04 23:33

>>5
What about my gay?

Name: Anonymous 2010-03-05 0:00

>>4
No, look, the onus is probably on you here, for positing the solution, but I'll go ahead anyway.

A common demonstration of the halting problem is to suppose that a candidate Turing Machine (TM) for solving the halting problem is modified to exit if it determines that the TM it is analyzing will not halt. If it determines that the analyzed TM will halt, it goes into an infinite loop. This is a simple enough modification that any /prog/lodyte could muster.

Obviously, when applied to itself, the candidate fails and must be rejected. This is true of any candidate, and moreover, any candidate without modification must also be able to accurately evaluate the modified candidate. So all unmodified candidates fail for this case.

To show this applies to all finitely expressible TMs, presume the existence of a finitely-expressible candidate TM, and make the modification, which shall not introduce an infinite requirement. In this case, it is as simple as the case above: all candidates are unsuitable.

If you chose to reject this on the grounds that no finitely expressible TM can suitable to serve as a candidate, then it is as simple as that: there is no finite-resource scenario for solving the halting problem.

Q.E. friggin' D.

Name: Anonymous 2010-03-05 0:04

[b][i]HAX MY ONUS[i][/b]

Name: Anonymous 2010-03-05 0:41

Obviously, when applied to itself, the candidate fails and must be rejected.

Wait, wait wait wait, let me make sure I'm following you here.

So by "applied to itself", you mean applying the Halt-detector TM on itself recursively, such that the Halt-detector is now determining whether or not the Halt-detector will halt, correct? And you're then saying that the Halt-detector will determine that the Halt-detector will fail -- does that mean the Halt-detector will be able to correctly determine that it has been made to start an infinite recursion and will therefore end the recursion (or, maybe, never evaluate in the first place)? Or does that mean it will continue to go into a loop because it has been made to do so, even though it should be exiting because it will never halt?



I'm not >>4-san, just an outside observer.

Name: Anonymous 2010-03-05 5:48

>>7
If it determines that the analyzed TM will halt, it goes into an infinite loop.
Obviously you don't see the circular reasoning here. In a environment with finite resources, a TM may enter into an "infinite loop", however we can easily and accurately determine if such a loop has been entered into. Consider a finite set of states and state transitions (implied by finite resources). We can simply mark a state as visited upon execution, and if any state is visited more than once we have detected a loop and exit. The program must eventually return, or visit an already visited state. In such a case, the program will loop forever but we have successfully ascertained the result and can now do what we wish with it (whether that be, to ourselves loop infinitely or return doesn't matter.) In fact, the entire argument that humans can solve the halting problem is based on anecdotal evidence of us examining our own programs or some such, but any such program will have such a microscopic number of states that it is completely laughable to say is non-computable.

Name: Anonymous 2010-03-05 8:16

Humans are just highly non-deterministic TM's, but if someone could manage to reverse engineer the human mind well enough and figure out all the state it contains, it should be possible to emulate it slowly on a TM (and maybe faster on hardware closer to its model).

Name: Anonymous 2010-03-05 8:59

>>9
Yep, that's the idea.

>>10
a TM may enter into an "infinite loop", however we can easily and accurately determine if such a loop has been entered into.
By 'we' do you mean 'humans' or do you mean there is an algorithm that will do so? If the latter, feel free to man up and show this.

More importantly,
Obviously you don't see the circular reasoning here.
I am not using circular reasoning, but I'm happy to admit that the task described is a somewhat 'circular' one, or better: recursively contradictory. You can object to it all you want, but such a task is sensical, coherent and finitely expressible.

Name: Anonymous 2010-03-05 9:06

>>10
however we can easily and accurately determine if such a loop has been entered into.
This would be so remarkable, I'd really like to see a proof of it. Computing many computable real numbers doesn't seem to be a loop of the kind you are describing.

Name: Anonymous 2010-03-05 9:46

I present to all y'alls the Magnificent Busy Beaver!

http://en.wikipedia.org/wiki/Busy_beaver

Now everyone who thinks that humans are able to solve halting problem, at least for small problem sizes, is welcome to follow the external link to the BB database, take one of the ~30 yet unsolved Beavers of size 5 -- that's a 5-state Touring machine on binary alphabet, pretty "microscopic" if you ask me, even smaller than your penis -- and use your mighty non-classical reasoning powers to determine if is it halting.

Name: Anonymous 2010-03-05 9:50

Also, >>10 mixed up the resources needed to run a machine and the exponentially more resources required to mark visited states, or rather not just visited states, because then we can still impose a limit on the running time, but all possible states, in case when we are interested if the machine is guaranteed to stop on any input.

Name: Anonymous 2010-03-05 9:51

>>12
I tried to explain it in natural language but apparently not.
Let S be the enumeration all possible states of a chosen "TM", and A the enumeration of all state transitions of such a "TM", A = {(S1,S2), (S2, S3), ...}
Given that each state requires a non-zero amount of memory S must be finite for all "TM's" with finite memory. With this in mind it's trivial to construct an algorithm which tests whether a given program halts or not.

Set visited(Sn) = false for all states. Set s ∈ S = entry state, {g1, g2, g3, ... gn} ∈ S = exit state. While the current state is not visited and not an exit state, mark it as visited and traverse to the next state (run the next discrete step in the program). If the current state is an exit state, the program does not loop, we are done. If the current state is already visited, the program must loop, we are similarly done.

This will always give us a result in finite time (an inductive proof of this is left as an exercise for the reader, chiefly that the number of unvisited states must be strictly lower at every step of the program and thus must eventually be exhausted.)

Name: Anonymous 2010-03-05 10:02

>>15
I'll add some anecdotal evidence to dispute this. I personally "solve" the halting problem in exactly the manner described, but use a number of heuristics to reduce the set of states needed to be checked for loops down to three or four before doing any transition and seen-this-state-before-will-never-terminate analysis. This tends to be a "good enough" approach for real world programming but the fact that we are using an admissible heuristic will cause occasional problems in this method (and I'm sure you get them on a weekly basis). Saying that it is "impractical" is utter nonsense, a computer could use such a heuristic also however much like isProbablePrime() it turns out to be not so useful when we want a deterministic machine to output a definite yes or no answer for us.

Name: Anonymous 2010-03-05 10:45

Since recursion and looping have been brought up, let us use strict definitions.  A program that will halt on certain input can iterate upon itself as many times as necessary and make however many calculations, including the same calculations, as many times as necessary before finally halting.  Finally halting.  A program that does not halt on certain input can iterate upon itself and make however many calculations but will never halt (will never return).

Any heuristics that impose a time limit or a loop limit on this problem defeats the purpose of a Universal Turing Machine that definitely proves whether any valid input on any computable program lets that program halt.  Deterministic finite-state automata don't work that way and such assumptions escape the thought experiment entirely by allowing a state which we don't consider a part of the permit solutions - "give up."

If I may conjecture, saying that we allow "give up" seems to imply our intended result anyway.  We can not build a Turing Machine that can satisfy the halting problem.

Name: Anonymous 2010-03-05 11:18

For fuck's sake, not The Emperor's New Mind. In the same book he made the argument that the Chinese room experiment means an algorithmic description of consciousness is impossible because he doesn't understand it.
Don't waste your time on Penrose. He's a mediocre mathematician and an absolutely shit cognitive scientist.

Name: Anonymous 2010-03-05 11:52

>>17
Dude. If you don't want to mess with the Busy Beaver, here is another program for you

def f():
    z = 0
    while True:
        z += 1
        for x in xrange(1, z):
            for y in xrange(1, x + 1):
                 if x**4 + y**4 == z**4:
                      return x, y, z

Show your "state enumerating principle" in action. What? Problems? Can't even begin?

That's because the "heuristics" you are talking are only applicable to various glorified "Hello world!" programs, a few simple loops and that's all. When people talk about nontrivial cases of halting problem, about time complexity or decidability of a typechecking/inferencing algorithm, they don't mean this kindergarten stuff.

All interesting programs have structure similar to this, even fucking fibs can be proven to terminate only by inventing and verifying a hypothesis about certain invariants in the data it operates on, not by "checking states for loops".

Pfff, what a moron.

Name: Anonymous 2010-03-05 13:27

EXPRESS MY ANUS

Name: Anonymous 2010-03-05 13:35

>>20
I agree with you, tough guy. However the last line was uncalled for and undermines the value of you're exposition.

P.S.: I think somebody mentioned that tracking whether you hit a repeated state takes a lot more space than the machine your analyzing in the first place. Theres a more efficient way to approach the problem: if you have, say, 40 memory bits and 8 states, well thats 43 bits of total state. So either you halt in 243 steps or you never do it. To keep track of this, you only need as much memory as the original machine has, for a standard step counter.

Name: Anonymous 2010-03-05 13:59

% make love
make: *** No rule to make target `love'.  Stop.

;_;

Name: Anonymous 2010-03-05 14:16

>>23
cat >> Makefile
love:
        @echo Ungh ungh ungh
^D

Name: Anonymous 2010-03-05 14:18

>>22
This seems wrong to me. Find the first sequence of 30 nines in the decimal expansion of pi, for example. We don't know if it exists. But just because we can build a computer with n stateful bits for this program doesn't mean it must halt in 2n steps. It could halt sooner, or it could never halt. Silly.

Name: Anonymous 2010-03-05 14:29

>>16
This will always give us a result in finite time (an inductive proof of this is left as an exercise for the reader, chiefly that the number of unvisited states must be strictly lower at every step of the program and thus must eventually be exhausted.)

Per >>22 I would like to point out that there is always a problem in any scenario of finite resources to which this method cannot be successfully employed, even if it were correct. The fact is your procedure still falls apart completely when the candidate is asked to analyze itself, as previously illustrated.

In regards to >>17 I must point out that this is a case of 'good enough' isn't. If it works for you and maintains an acceptable quality of life such that you are not bothered by any inaccuracies, good on you, but it doesn't solve the halting problem. >>18 is relevant here, and I would like to add that addressing one instance or any limited collection of instances is not a solution. A solution addresses every possible instance with 100% consistency. (The probable finite nature of the universe notwithstanding, it must also address the infinite cases but I'm letting that one go.)

>>19
I get this every time I bring up Penrose. The issue isn't that there is something wrong with him--it's that there is something wrong with his argument. However, he's far better at both math and physics than I am and I'm just trying to exhaust his arguments until I am beyond 100% certain that the rabbit he's trying to pull from a hat is actually located some distance up his bottom.

(Actually, I do like Penrose. He's got some very takes on things. His hunt for quantum entanglement in the brain is obviously ill-founded, though, even if he's right about the non-computability bit.)

At this point I would like to apologize to >>5 who has taken issue with 'my' gay, for not being more clear up front. It is not that this topic can be expected to escape degenerating into a steaming shitfest on any board, but just look at the glorious shitfest that /prog/ has made of it. You will not find its particular likeness wrought of the same stuff on any other board.

Name: Anonymous 2010-03-05 14:30

>>25
Uhh? It will either halt in 2n steps (or less), or it will never halt. It's a upper bound on the amount of steps it can run until it revisits an older state, at which point it's guaranteed it won't halt.

Name: Anonymous 2010-03-05 14:51

>>25
doesn't mean it must halt in 2n steps. It could halt sooner, or it could never halt
Let M be the nonempty set of possible memory states. Let e \in M be the special state we call an end state. We call a function f: M -> M a program if f(e) = e. Let P be the set of all programs. We say that program p halts for input i, if there exists such natural number n that p^n(i) = e, where p^n means 'p iterated n times'.

Now say that our set of memory states is finite and it has q states.  Take any program p and any input i. Let S_n = p^n(i). Now, this program halts for input i if there is such index k, that S_k = e. Now let's read the sequence {S_n} from the beginning. Before reading q+1 terms, one of the following surely will happen:
1) We encounter the state e, and so our program halts.
2) We encounter a term on the position r that we encountered before on the position t - it means that for all natural i, S_r+i = S_t+i, and so our program loops forever.

Any questions?

Name: Anonymous 2010-03-05 15:01

>>28
I am not >>25-kun, but I have a question. When will /prog/ support LATEX->MathML conversions in place of BBCode?

Name: Anonymous 2010-03-05 15:04

>>29
NEVER, THIS FORUM IS ABOUT ABSTRACT BULLSHITE, NOT EXPRESSIBLE MATHEMATICS

Name: Anonymous 2010-03-05 15:06

>>30
>he still believes 0.999...=1

Name: Anonymous 2010-03-05 15:06

>>30
Observation: the major topic covered in this thread is mathematically expressible.

Name: Anonymous 2010-03-05 15:24

>>32
Hypothesis: every topic can be mathematically expressible.

Name: Anonymous 2010-03-05 15:37

>>16
Given that each state requires a non-zero amount of memory S must be finite for all "TM's" with finite memory.
Your proof is based on the assumption that TMs have finite memory, which they do not.

>>20
This is an example of a program with finite memory but infinite state, if you consider it in the strict mathematical sense. But if your machine integers have an upper bound, the states are finite and can be enumerated. It is trivial to show that in a finite time, a program with finite memory and state must either halt or enter an infinite loop.

Name: Anonymous 2010-03-05 15:38

>>33
Hypothesis: my anus can be mathematically expressible.

Name: Anonymous 2010-03-05 15:53

>>34
Your proof is based on the assumption that TMs have finite memory, which they do not.
Oh yeah, because we're bound to one and only definition and it's of course impossible to generalize.

Name: Anonymous 2010-03-05 15:58

>>34
>>16 has been arguing that bringing the issue into a finite-resource scenario changes the game completely. We have been letting him have his finite-resource scenario because it does not, in fact, change the game. You'll find a few points about that somewhere in >>26 -- but yes, I'd rather we got back to the proper case for the sake of simplicity.

At this point, I'd also like to add that the task of enumerating states of a finite-state TM has not been solved either.

Name: Anonymous 2010-03-05 17:50

>>28
>>22
Maybe I didn't stress it enough in >>15: we rarely encounter a question like "Does this program terminate on the input of 12343?", in this exact form. We usually are interested in questions that are like "Does the program halt for all possible inputs?". Because we want to run the program with some input and we'd like to know in advance if it halts.

To directly evaluate the program on all possible inputs limited by some N, you need both exponential time and space.

Name: Anonymous 2010-03-05 17:51

>>37
Bringing the issue into a finite-resource scenario actually transforms the question into P?=NP.

Name: Anonymous 2010-03-05 17:58

>>26
You see, the fact that Penrose can't comprehend the Chinese Room thought experiment completely invalidates anything he has to say about consciousness. Because then he talks about the Consciousness™ (like RMS talks about Freedom™), which is not at all like the actual consciousness that we all directly experience.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -