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.
>>77
Well it was high up enough on the page really. Other than that, if I'd realized the 'optimizing the bbcode' thread was threadstopped I would have bumped it, but I didn't notice 'til after. Now it wouldn't matter because the old thread got bumped and we even have a new one too!
>>79
To be fair it wasn't the real halting problem and it can't be proved impossible to solve in the standard way... and I don't think anyone was really trolling.
Name:
Anonymous2010-03-11 18:26
I am confused by the assertion that the Halting Problem is unsolvable for Turing Machines with a finite tape. Surely you could enumerate all the possible "super-states" (i.e. a subset of TM states × tape × alphabet) of such a bounded TM and thereby determine if the TM ever entered a loop?
>>82
Yes, you could. I'm not sure why such an obviously false assertation would confuse you.
Name:
Anonymous2010-03-11 18:50
>>82
But Turing Machines do not have finite tape. Having an "infinite tape" means that any size program of any complexity can be emulated on it. You can argue that it isn't possible to write a program that has an infinite number of states, which makes more sense. So, let us assume a situation where the program does not enter a state more than twice.
Instead of a program, a thread performs some task but enters a situation where it needs to perform more tasks before it can proceed. It creates and runs a recursive thread on what is left over and has to wait for that new thread to "join." We shall assume that this is the top level. Our Turing Machine will prove whether this top level original thread ever finishes. So now you're in a situation where the Turing Machine has to simulate itself.
Name:
Anonymous2010-03-11 19:05
>>84
Sorry, I should have added: I know my admittedly hasty experiment violates a major rule of the Halting problem - that the Turing Machine automatically replies "stops" or "loops" - and any actually running of the program P on input I is considered hypothetically; but, the standard definition of the Halting problem and of a Turing Machine are not a part of your concern anyway.
>>92
Oh really? Anything else is meaningless. Separating the two TMs means we're no longer speaking about any kind of universe of computation, but some arbitrary setup that says nothing at all about general computability--the issue at hand.
Anyway, >>27 is trying to enumerate states. Infodynamics applies to this kind of procedure, and the jig is up once entropy is maximal and resource pressure forces an infinite loop or termination.
This is why >>92 doesn't want to run both TMs from the same tape: solving the problem in finite space is only possible by removing a class containing all of the principally insoluble cases (including the candidate TM itself!) Recast to the infinite case, this would have the effect of removing Turing Completeness, so it's easy to see that we're no longer talking about Turing Machines with limited resources, we're talking about something else.
At this point the problem is no longer interesting for any of the same reasons. The machines just aren't TC any longer, and the problem space isn't related to completeness in any form.
Name:
Anonymous2010-03-13 9:35
>>103 At this point the problem is no longer interesting for any of the same reasons. The machines just aren't TC any longer
You must find DFAs, PDAs, and LBAs a real bore then.
grep wouldn't have worked if there was some unexpected difference in the input - letter case, extra punctuation, spacing. But that's neither here nor there, I didn't care enough to actually look for it.
Name:
Anonymous2010-03-13 9:47
>>105
That's not an md5 sum. It's a bunch of [m][o][/m] tags
>>109
Three reasons:
1. grep doesn't implement look-ahead in PCRE mode
2. Your pattern only makes post-pattern assertions about the mailto, and (if it worked) would not display the contents with -o (without -o, you get a bunch of garbage you don't care about)
3. There is a chance that the MD5 sum begins (or ends) with "sage" (hence the \" in my pattern (and the : in the grep -v))
Of course the real solution is to compute the hash and grep for "mailto:$hash" but that isn't nearly ENTERPRISE enough.
Name:
Anonymous2010-03-13 18:56
1. Use perl -ne 'print if /mailto:(?!sage)/' and do that all in one step. Why fork two processes? grep's PCRE mode sucks anyway.
2. Point irrelevant if not using grep. Aside from that, your solution is broken, because the existence of the word "sage" anywhere will cause the line to fail to display.
3. The canonical form of an md5sum is 32 hexadecimal characters, but good point anyway, you're thinking outside the box and that's a good thing; sure, maybe it was base 32 or base 64 encoded instead of base 16. /mailto:(?!sage")/ it is, then.
And of course the real solution is to extract the e-mail fields using an HTML parser, and pipe through sort -u. As already stated, searching for a precomputed hash is a terrible! solution because there is a good chance that the input you use is different than that used to create the md5sum you're searching for. Capitalization chance is possible, although unlikely, that this might be different than advertised. Punctuation might be different -- are the quotation marks included? Line endings could certainly be different. Did you use echo or echo -n? If there is a newline, is it \r\n or \n?
Name:
Anonymous2010-03-13 19:04
And here is that real solution, which I just hacked together and verified:
import urllib2, BeautifulSoup, re
set(tag['href']
for tag in (BeautifulSoup.BeautifulSoup
(urllib2.urlopen('http://dis.4chan.org/read/prog/1267755680/').read())
.findAll('a', href=re.compile(r'mailto:(?!sage$)(.*)'))))
>>111 perl -ne 'print if /mailto:(?!sage)/'
Fails point 2. Also invokes perl.
the existence of the word "sage" anywhere
No, the existence of :sage just before the first ". I pointed this out already. : isn't an alphanum, so it won't appear in the hash.
there is a good chance that the input you use is different than that used to create the md5sum you're searching for
``YHBT'' only has one md5sum... that's kind of the point.