Computation: How deep does the rabbit hole go?

Wikipedia, a Trap for the Curious Mind

I lost track of a couple of hours yesterday going down Wikipedia’s bunny trail.

It all started innocently enough with a self emailed post on an implementation of Conway’s game of life in html 5. Reading about the rules reminded me of Stephen Wolfram’s a New Kind of Science, so I explored a related page on Glider Guns, then cellular automatons, then Turing Machines, unification with Lambda calculus, and finally landed on a page that has been a splinter in my mind for the past 16 hours.

The page describes David Hilbert’s proposal of  Entsheidungsproblem.

The Entscheidungsproblem asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either “True ” or “False” according to whether the statement is true or false”

source

Without a means of proving equivalence, I questioned how far we could take any computational model.

“Hey, I have this answer but I can’t tell you that it’s right”. Confidence in the truth of a solution is one of my instinctual tests of algorithm utility, otherwise it’s just mental masturbation.

For more specific conditions equivalence can indeed be proven.

Some first – order theories are algorithmically decidable ; examples of this include Presburger arithmetic , real closed fields and static type systems of (most ) programming languages . The general first – order theory of the natural numbers expressed in Peano’s axioms cannot be decided with such an algorithm , however.

Share and Enjoy:
  • Digg
  • Facebook
  • Google Bookmarks
  • HackerNews
  • Reddit
  • StumbleUpon
  • Twitter

About Mark Essel

I’m Mark Essel, a dataminer & systems engineer that’s added cofounder, web developer and author to my bag of tricks. My quest is to rediscover my life’s passions, and leverage that drive into profitable business ventures.
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.
  • Leland

    Mark… i don't really have a reply to your question on how deep the computation hole goes… but you brought up a machine that takes in natural language and outputs a true/false statement. It made me think… perhaps machines that can accurately interpret natural language are going to be the main jumping point for our plunge into a fully AI controlled world?

    Now that I think about it, one of the most important and fundamental aspects of our lives is the ability to communicate. Living in a foreign country has thrown this in my face every day and I am acutely aware of it.

    Once there is a standardized library for the accurate understanding of spoken language, is there any job that a machine couldn't theoretically do?

    Besides purely mental pursuits and jobs that require face to face human interaction for their success, *many* of the jobs our current economy is based on could easily be replaced by a machine that can accurately understand language.

    For example, a cook… because they are hidden away in the kitchen usually, having a “cooking assembly line” would save huge percentages of money on wasted food, salaries and mistakes in the creation of food. I can see resteraunts being run solely on their waiting staff in the future.

    Considering this point, I believe that our ramp into the first true “strong” AI systems will follow the process of human jobs being increasingly abstract and less “hands on”. As the years go by, jobs that initially required someone to actually use their hands to build or make something will become more abstract. For example, a cook would design the chemical structure/taste of the food instead of actually cook it. A car mechanic would create new processes for more efficient car repairs instead of actually fixing a car.

    It will be a gradual slope… all of a sudden, we will realize that our machine counterparts will have reached our highest level of abstraction and then they will surpass us.

    I think this gradual slope of the development of abstractive capability of machines will allow for a smooth transition into a singularity style event. To be honest, the world in the next thirty years is going to be like nothing ever before seen in the history of the universe (I am of the belief that at least in our multiverse, another race of beings near our technological level, if given a few thousands years more then us, would have covered the entire multiverse with knowledge and understanding already… thats the speed with which a future AI based society can change their physical reality).

  • http://www.victusspiritus.com/ Mark Essel

    Far out Leland, I'm excited about the development an application of strong AI as well.

  • http://www.victusspiritus.com/ Mark Essel

    Updated my earlier comment after finding some more time.

blog comments powered by Disqus