Transcript KaplanPsyOrf322S05Presentation

Humans, Computers, and
Computational
Complexity
J. Winters Brock
Nathan Kaplan
Jason Thompson


Can computer programs answer our questions?
Can computer programs answer them quickly?
Theory of everything:
“A finite set of principles from which one
could mindlessly deduce all mathematical
truths, by merely tediously following the
rules of symbolic logic.”
Turing’s Halting Problem

Will my computer program run into an infinite
loop?
“Given a description of an algorithm and its initial input, determine
whether the algorithm, when executed on this input, ever halts.
The alternative is that it runs forever without halting.”

1936 – Alan Turing showed a general algorithm
to solve the problem for all inputs cannot exist.
Elegant LISP Programs

Turing’s proof was abstract, let’s take a real
proof on a real machine.
A program is “elegant” if no shorter program
produces the same output.

Chaitin shows with a similar paradox that it is
impossible to prove that any particular large
program is “elegant.”
Boolean Satisfiability
Boolean Statement: A statement that is formed
from variables, parentheses, and the logical
connectors, AND, OR, NOT.
(A V ¬B V ¬C) ^ (A V B V ¬C) ^ (¬A V B V C)
Can you assign true and false values to A, B, and C
in order to make the whole statement true?

Humans have problems with a problem of this
nature, however computers can check all the
possibilities in order to answer the question.

Effectively checkable
Can we find a more efficient algorithm?

P vs. NP


P: The set of all problems that can be solved by
a computer program in polynomial time.
NP: The set of all problems that can be solved
by a nondeterministic program in polynomial
time. (effectively checkable)




NP-complete: A problem that is in NP that
every other problem in NP can be reduced to.
Cook’s Theorem
Polynomial time algorithm for any NP-complete
problem → P = NP
Majority believe P ≠ NP




Are the algorithmic boundaries of computer
computation applicable to human reasoning?
Computationalism: the view that all human
activities are reducible to algorithms and
therefore, could be implemented by a computer
Anti-computationalism: cognition is not
computational
Pluralism: much of reasoning is computational,
but some is not
Searle’s Chinese Room Thought
Experiment



“Imagine that you carry out the steps in a program for answering questions in a language you do
not understand. I do not understand Chinese, so I imagine that I am locked in a room with a lot
of boxes of Chinese symbols (the database), I get small bunches of Chinese symbols passed to
me (questions in Chinese), and I look up in a rule book (the program) what I am supposed to do.
I perform certain operations on the symbols in accordance with the rules (that is, I carry out the
steps in the program) and give back small bunches of symbols (answers to the questions) to those
outside the room. I am the computer implementing a program for answering questions in
Chinese, but all the same I do not understand a word of Chinese. (Ftrain.com)”
Entire process is syntactical
Syntax does not guarantee understanding/semantics
No matter how seemingly intelligent you may be, the fact still
remains that the process is meaningless to you and that you lack
comprehension. This lack is what we know as the “intentional
mental state.”
Language Processing


For humans, it comes naturally.
Machines are not as efficient as humans in this
area.
“Buffalo buffalo buffalo buffalo.”

Lexical Functional Grammar (LFG) recognition
is NP-hard.