Principles of Computing

 

Theorems or Adages

• No Free Lunch theorem - there is always a trade-off; originally proposed in the context of search and optimization
• Black swan theory - theory on seemingly unexpected grand events
• Hofstadter’s law - "It always takes longer than expected, even if you take into consideration the Hofstadter’s law."
• Murphy’s law - "Anything that can go wrong will go wrong."
• Infinite monkey theorem
• The Chinese Room Argument - [discussed under Linguistics]
• Pigeonhole principle
• Moravec’s paradox - While hard tasks such as playing Go, logical reasoning, algebra are easy for AI systems, easy tasks such as moving an object, using common-sense are hard for AI systems.
• AI effect refers to the tendency for onlookers to dismiss (artificial) intelligence for sheer brute force, number crunching or plain computation. This effect is also observable in magic when the trick gets revealed to the audience.
• Church-Turing Thesis - Can a Turing machine compute everything that is computable? What is an algorithm? The Church-Turing thesis states that the Turing Machine model is at least as powerful as any computer that can be built in practice. The Church-Turing thesis states that known programming languages are capable of describing everything that could be described as an algorithm. In other words, it says the conventional definition of "algorithm" as that which can be done by executing programs-as-we-know-them is the right definition.
• Turing-completeness - In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any single-tape Turing machine. So, if somebody says "my new thing is Turing-complete" that means in principle (although often not in practice) it could be used to solve any computation problem. A basic calculator or a scientific calculator is not Turing-complete. Programming languages are similar to those machines (although virtual). They take programs and run them. Most programming languages, conventional and unconventional, such as C, Java, Lisp, Haskell and Prolog, are Turing-complete. The typesetting language LaTeX is also Turing-complete. However, markup languages such as XML and HTML are non-Turing-complete languages. Formal languages such as regular languages and context-free languages are Turing complete. On the other hand, logics such as propositional logic and predicate logic are not Turing complete.
• AI-complete - The hardest problems in AI (such as vision, natural language understanding, and planning) are AI-complete. In other words, solving an AI-complete problem is equivalent to making computers as intelligent as people.
• Strong AI vs. Weak AI - Strong AI is general AI (a.k.a. AGI) that can perform any intellectual task that a human being can. Weak AI (a.k.a. narrow AI) is AI that can perform specific intellectual tasks (e.g. IBM Watson).
• Friendly AI - FAI is general AI that would have a positive impact, rather than a negative effect, on humanity. The closely-related areas are machine ethics and AI takeover.
• Colossal Disaster - IBM Watson is merely a massive engineering (and marketing) effort comprised of heavy parallelism, huge knowledge base and clusters. The technologies that power Watson include (1) information retrieval and information extraction, (2) computational linguistics (statistical paraphrasing, semantic role labelling), (3) machine learning and (4) knowledge representation and reasoning (temporal reasoning, geospatial reasoning). Watson is expert at playing Jeopardy!. So maybe it is an expert system. But is it an AI system? Roger Schank doesn’t think so because it is yet to display intelligence. If it were an AI system then it should be able to answer the following kinds of questions: (1) between Jim and Betty, who is the better person to lead our new social initiative while creating a more transparent culture, (2) can you create an operational strategy to achieve these revenue objectives, (3) how would you rate the CEO’s speech on employee morale?, (4) how do you think this marketing campaign will impact our customers and prospective customers, or (6) was Jim’s joke funny? These questions pertain to request for opinion, strategy and complex phenomena such as morale, jokes, feeling and emotions.
• Recommender systems - The technosphere is filled with recommender systems such as Google search, Facebook feed, Twitter feed, YouTube video recommendation and Amazon product recommendation.

Computer Languages

• General Purpose Programming Language: C (procedural programming, ancient); Java (no pointers, garbage collector, enterprise language, statically typed, Hibernate database application framework, Struts and Spring web application frameworks); Scala (object-oriented + functional programming, statically typed); C++ (object-oriented programming)
• Scripting Language: Python (dynamically typed, Django web application framework); awk (structured text search and replace)
• Functional Language: Haskell (functional programming, statically typed)
• Logical Language: Prolog (logic programming)
• Query Language: SQL (query rdbms database); XPath (query xml database)
• Shell Programming Language: bash (run commands from script)
• Data Language: HTML (exchange data, common in www); XML (exchange data)
• Modelling Language: RDFS (less expressive modelling); OWL (more expressive modelling)