Here is a bit of mathematical logic for you - an accessible presentation of Turing's proof that the halting problem ("will a given computer program with a given input stop") is undecidable. It's just a proof by contradiction, with a recursive aspect similar to the work of Godel.
To try to simplify his already simple explanation, assume we can identify when a program would halt and consider a program P that loops forever when fed somethings that halts and exits otherwise. Then, feed P to itself - for it to stop, it would have to loop forever, and vice-versa. Contradiction, therefore we cannot identify when a program would halt.
If you want a fuller explanation, read the linked resource. As an aside, the copyright notice at the top of it is a little unsettling, but I decided to share it nonetheless as it is well written. But for reference, all works are implicitly copyrighted, and in my book if you're going to make an explicit declaration regarding intellectual property you're best off choosing some sort of "libre" license (but still retaining your copyright of course).
Sunday, December 26, 2010
Sunday, December 19, 2010
Nexus S Review
Many moons ago I reviewed the T-Mobile G1, the launch device for Android. In a nutshell, I said it was a fun geeky gadget, a decent phone, and that Android was "poised to make significant impact in the mobile market."
Two years later it is clear that Android has been even larger than most would have expected. But while I am happy with the progress of Android as a whole, I am saddened by the actual devices on the market. Phones are no longer geeky gadgets - they are supposedly "sexy" devices with smooth curves and shiny screens.
The reason for this is clear - Apple. Where they go consumers follow, and so other manufacturers desperately try to mimic them. Efficacy aside, this strategy leads to a lack of diversity (in this case, buttons) in the market. Compound this with the predilection of manufacturers to load up bloatware on Android devices (the two-edged sword of openness, or "why I'm a GPL guy"), and you end up with many phones that are all significantly flawed in some way or another.
A "developer phone", with collaboration from Google, is supposed to address these issues. It should be cutting edge and functional in design, not an imitation. And it should be "pure Google", without uninstallable bloatware, UI tweaks, and other annoyances.
The Nexus S utterly fails on the first front, and could be better on the second. It looks beautiful - shiny, sleek, it's quite attractive for something I keep in my pockets 95% of the time. Personally I've never understood wanting excessively flashy gadgets - I have no need to impress strangers in coffee shops, and would rather not attract mugging-worthy attention in general. If the goal of manufacturers is to create things for art museums then they're on that track, but if they want to make functional phones then they need to change direction a bit.
The specific design issue with the Nexus S is that it is just entirely seamless, with no true buttons - the four standard Android keys only appear when the screen is on and offer no tactile feedback ("haptic" feedback is an irritating battery-waster). No trackball/touchpad, no camera button - just a power button on the right and a volume rocker on the left. And the whole phone is so nondescript that it's difficult to tell orientation by feel (or indeed even when looking at it, if the screen is off).
Samsung used a more plastic-feeling casing than most other manufacturers, though I will admit the phone still feels durable enough. However it is also totally glossy, even on the back - this combined with the slight curve makes one worry about it squeezing out of your hand (as well as attracting fingerprints).
Another huge step backwards - no passive notification. The Nexus S lacks an LED that blinks when you receive an alert (message, calendar, etc.) - so, if muted, there is no way to know. This decision boggles me the most as they could have included such a feature without compromising their "sexy"design.
Now, the "pure Google"failure is less severe. In fact, I suppose it's not a failure at all, as the phone is indeed only preloaded with Google software. However, just like non-Google Android phones, some of the software is uninstallable. Defining a certain set of true core apps (browser, maps, email, chat, dialer, calculator, etc.) makes sense, but certain others (Latitude, Places, Earth, Voice) aren't something every user will always want and should be removable. I'm hopeful that this situation will change, but as of release it seems that there are still apps you cannot get rid of.
Overall, this phone epitomizes my disappointment with the industry. It's really just a mildly improved Galaxy S phone - the front-facing camera and NFC are supposedly "next-gen" features. Meanwhile true next-gen features - 4G and dual-core processor - are omitted, along with the above lamented "last-gen" features of buttons and passive indication.
The screen is bright and attractive, the device is fast and slick, Android is a great OS, and there are apps for anything you may want. But the Nexus S is not a worthy successor to the G1 - while touch screen and voice input have improved, you still need tactile buttons to do anything that involves creation. Pure touch is great for consumption, pinching and flicking and selecting options - but if you want to enter any serious amount of text (I enjoy chatting on my phone), it's just lacking. One might offer the G2 as a G1 successor, but while it has a keyboard, 4G, and is named similarly, it is not the "official" developer phone and as such is more locked down.
Sadly I see this trend continuing, and the gulf between touch/non-touch growing wider as tablets are popularized. Being pure-touch allows the device to be sleek and attractive and thus sell better, and for most people who really do just consume media it will be adequate - a tablet could replace a computer for such a user. But for anyone who tries to create content rather than just consume, a real keyboard is needed - let's hope they don't go the same way as cellphones with buttons.
Two years later it is clear that Android has been even larger than most would have expected. But while I am happy with the progress of Android as a whole, I am saddened by the actual devices on the market. Phones are no longer geeky gadgets - they are supposedly "sexy" devices with smooth curves and shiny screens.
The reason for this is clear - Apple. Where they go consumers follow, and so other manufacturers desperately try to mimic them. Efficacy aside, this strategy leads to a lack of diversity (in this case, buttons) in the market. Compound this with the predilection of manufacturers to load up bloatware on Android devices (the two-edged sword of openness, or "why I'm a GPL guy"), and you end up with many phones that are all significantly flawed in some way or another.
A "developer phone", with collaboration from Google, is supposed to address these issues. It should be cutting edge and functional in design, not an imitation. And it should be "pure Google", without uninstallable bloatware, UI tweaks, and other annoyances.
The Nexus S utterly fails on the first front, and could be better on the second. It looks beautiful - shiny, sleek, it's quite attractive for something I keep in my pockets 95% of the time. Personally I've never understood wanting excessively flashy gadgets - I have no need to impress strangers in coffee shops, and would rather not attract mugging-worthy attention in general. If the goal of manufacturers is to create things for art museums then they're on that track, but if they want to make functional phones then they need to change direction a bit.
The specific design issue with the Nexus S is that it is just entirely seamless, with no true buttons - the four standard Android keys only appear when the screen is on and offer no tactile feedback ("haptic" feedback is an irritating battery-waster). No trackball/touchpad, no camera button - just a power button on the right and a volume rocker on the left. And the whole phone is so nondescript that it's difficult to tell orientation by feel (or indeed even when looking at it, if the screen is off).
Samsung used a more plastic-feeling casing than most other manufacturers, though I will admit the phone still feels durable enough. However it is also totally glossy, even on the back - this combined with the slight curve makes one worry about it squeezing out of your hand (as well as attracting fingerprints).
Another huge step backwards - no passive notification. The Nexus S lacks an LED that blinks when you receive an alert (message, calendar, etc.) - so, if muted, there is no way to know. This decision boggles me the most as they could have included such a feature without compromising their "sexy"design.
Now, the "pure Google"failure is less severe. In fact, I suppose it's not a failure at all, as the phone is indeed only preloaded with Google software. However, just like non-Google Android phones, some of the software is uninstallable. Defining a certain set of true core apps (browser, maps, email, chat, dialer, calculator, etc.) makes sense, but certain others (Latitude, Places, Earth, Voice) aren't something every user will always want and should be removable. I'm hopeful that this situation will change, but as of release it seems that there are still apps you cannot get rid of.
Overall, this phone epitomizes my disappointment with the industry. It's really just a mildly improved Galaxy S phone - the front-facing camera and NFC are supposedly "next-gen" features. Meanwhile true next-gen features - 4G and dual-core processor - are omitted, along with the above lamented "last-gen" features of buttons and passive indication.
The screen is bright and attractive, the device is fast and slick, Android is a great OS, and there are apps for anything you may want. But the Nexus S is not a worthy successor to the G1 - while touch screen and voice input have improved, you still need tactile buttons to do anything that involves creation. Pure touch is great for consumption, pinching and flicking and selecting options - but if you want to enter any serious amount of text (I enjoy chatting on my phone), it's just lacking. One might offer the G2 as a G1 successor, but while it has a keyboard, 4G, and is named similarly, it is not the "official" developer phone and as such is more locked down.
Sadly I see this trend continuing, and the gulf between touch/non-touch growing wider as tablets are popularized. Being pure-touch allows the device to be sleek and attractive and thus sell better, and for most people who really do just consume media it will be adequate - a tablet could replace a computer for such a user. But for anyone who tries to create content rather than just consume, a real keyboard is needed - let's hope they don't go the same way as cellphones with buttons.
Labels:
android,
apple,
cell phone,
linux,
nexus s,
open source,
review,
smart phone,
t-mobile g1
Sunday, December 12, 2010
Computers, language, and "Artificial" Intelligence
"AI is whatever hasn't been done yet."
This cynically clever quote is known as Tesler's Theorem, and it reflects the difficulty in convincing a human that a machine is intelligent. Chess is seen as a game requiring intelligence, but as computers gained dominance it was argued that they were just using "brute force" and not really "thinking" the same way we do. So when Deep Blue beat Kasparov, it somehow didn't count - computers were still not intelligent, just really fast.
Is there anything that will overcome this skepticism? The Turing Test seems the most likely candidate, as it is expressly designed to "fool" a human into sympathy - but once the computer is revealed many people will still claim that it is just a clever facsimile that doesn't really "feel" the words it says.
Our desire to refute artificial intelligence has deep philosophical and psychological roots - acknowledging intelligence created by our own hand raises many questions about our own nature and origins. And like many things, it would also challenge traditional religious views - would these AIs have "souls"? If not, then do we?
But my goal is not to confront these questions - intelligence is multifaceted, and despite human skepticism it is clear that computers have already achieved a great deal of intelligence in many areas. My question is not what is intelligence nor why exactly people don't want computers to have it, but rather what area has the most potential for AI development.
And, as the title suggests, I would offer language as that area. More precisely, natural language processing - having the computer "just do" what you tell it to - is both very interesting and also obviously practical. This may seem like a "Star Trek" concept, but we actually already have made a lot of progress with it.
For example, consider search engines - they have evolved from simple lookup mechanisms to genuine attempts to parse language. I must confess mixed feelings on this - as search engines increasingly target poorly formed queries, I find my own queries are sometimes "corrected" in an erroneous fashion. But the concept is a sound one - the search engine should truly understand your intent, and not just the literal meaning of your query.
Another example is recent progress with Mathematica. The latest release of Mathematica supports "free-form linguistics" - that is, "programming" with natural language (examples, more examples). I must again confess mixed feelings, in this case not because of false corrections but because Mathematica is a stalwart of closed source and overpriced software. I suppose search engines are also essentially closed source, but Mathematica in particular is depressing because so many of its peers are open.
But despite its proprietary nature, I must admit that Mathematica is an impressive piece of work. Eventually I expect many high level programming languages to support this sort of "fuzzy" syntax, where there are multiple ways to specify things and the interpreter makes assumptions based on context. Of course it will make mistakes, but it's not like programming is free of debugging today.
It will be interesting to see where these efforts go. I hope that eventually the sort of sophisticated language processing we are seeing becomes more open than it is now. And I expect that, once computers can be interacted with as naturally as humans, the great AI disputes and philosophical questions will fall away as people just start anthropomorphizing and treating their computer like a person. People want to treat things they interact with as humans, even if they don't want to think about the philosophical ramifications (see: pets, Disney movies, etc.).
This post has mostly been just a dump of interesting resources, so I may as well plug one more: Gödel, Escher, Bach: An Eternal Golden Braid
. Of course you've probably heard of it, and it was where I learned of Tesler's Theorem cited above. It also contains a dialogue "Etaoin Shrdlu", about the early but still sophisticated natural language processing program SHRDLU.
Thanks for reading.
This cynically clever quote is known as Tesler's Theorem, and it reflects the difficulty in convincing a human that a machine is intelligent. Chess is seen as a game requiring intelligence, but as computers gained dominance it was argued that they were just using "brute force" and not really "thinking" the same way we do. So when Deep Blue beat Kasparov, it somehow didn't count - computers were still not intelligent, just really fast.
Is there anything that will overcome this skepticism? The Turing Test seems the most likely candidate, as it is expressly designed to "fool" a human into sympathy - but once the computer is revealed many people will still claim that it is just a clever facsimile that doesn't really "feel" the words it says.
Our desire to refute artificial intelligence has deep philosophical and psychological roots - acknowledging intelligence created by our own hand raises many questions about our own nature and origins. And like many things, it would also challenge traditional religious views - would these AIs have "souls"? If not, then do we?
But my goal is not to confront these questions - intelligence is multifaceted, and despite human skepticism it is clear that computers have already achieved a great deal of intelligence in many areas. My question is not what is intelligence nor why exactly people don't want computers to have it, but rather what area has the most potential for AI development.
And, as the title suggests, I would offer language as that area. More precisely, natural language processing - having the computer "just do" what you tell it to - is both very interesting and also obviously practical. This may seem like a "Star Trek" concept, but we actually already have made a lot of progress with it.
For example, consider search engines - they have evolved from simple lookup mechanisms to genuine attempts to parse language. I must confess mixed feelings on this - as search engines increasingly target poorly formed queries, I find my own queries are sometimes "corrected" in an erroneous fashion. But the concept is a sound one - the search engine should truly understand your intent, and not just the literal meaning of your query.
Another example is recent progress with Mathematica. The latest release of Mathematica supports "free-form linguistics" - that is, "programming" with natural language (examples, more examples). I must again confess mixed feelings, in this case not because of false corrections but because Mathematica is a stalwart of closed source and overpriced software. I suppose search engines are also essentially closed source, but Mathematica in particular is depressing because so many of its peers are open.
But despite its proprietary nature, I must admit that Mathematica is an impressive piece of work. Eventually I expect many high level programming languages to support this sort of "fuzzy" syntax, where there are multiple ways to specify things and the interpreter makes assumptions based on context. Of course it will make mistakes, but it's not like programming is free of debugging today.
It will be interesting to see where these efforts go. I hope that eventually the sort of sophisticated language processing we are seeing becomes more open than it is now. And I expect that, once computers can be interacted with as naturally as humans, the great AI disputes and philosophical questions will fall away as people just start anthropomorphizing and treating their computer like a person. People want to treat things they interact with as humans, even if they don't want to think about the philosophical ramifications (see: pets, Disney movies, etc.).
This post has mostly been just a dump of interesting resources, so I may as well plug one more: Gödel, Escher, Bach: An Eternal Golden Braid
Thanks for reading.
Labels:
artificial intelligence,
language,
learning,
open source,
search engines
Sunday, December 5, 2010
Python Web Arcade
I've added a new project to Soycode - the Python Web Arcade. You can see it in action at the proles.net flash game arcade.
At the moment it's a very simple script which creates an even simpler site, but when the goal is to play web games the site design (and ads and etc.) should definitely take the back seat. All you need to host it is support for Python CGI - no SQL db or other nonsense required. The current functionality allows you to then use it as a custom auto post script with Mochi Media (a SF-based company offering over 15,000 flash games), meaning that once it's set up you can basically just explore and pick and choose from Mochi's game catalog, adding games to your site with a single click.
When the post request is made to the script, it does two main things. It first fetches the complete game feed and information from Mochi using Python Mochi. It then creates a page to display the game (example) and updates the index of your site with a thumbnail linking to that game page.
The site-making portion of the script is also capable of being run independently of adding a new game, in which case it checks your entire game library with the current Mochi repository and updates any games that are out of date. You can again run it from your browser using Python CGI, or you can execute the update directly from the command line (or cron it for convenience).
And that's it really - there's a healthy number of todos and known issues, but I hope this script is useful to others regardless. The main todo is making an admin interface of some sort that facilitates customization (at the moment you have to specify publish ID and other site aspects by editing the code - it's easy, but I suppose will still intimidate some). The main known issue is that not absolutely every Mochi game works - certain older games seem to not have the same sort of game_tag or otherwise fail with the Python Mochi package I am using.
But despite those caveats, I at least found this a fun and useful experience and hope others can as well. If nothing else, it's the only "flash web game arcade" script I'm aware of that is *not* written in PHP - which in my book is an excellent thing. In fact, the preponderance of PHP was the main reason I chose to write this at all, as I wanted something I could easily understand and customize. Python CGI turned out to be a very straightforward and pleasant experience, and I would suggest it for anyone looking to make a quick and simple "web app."
At the moment it's a very simple script which creates an even simpler site, but when the goal is to play web games the site design (and ads and etc.) should definitely take the back seat. All you need to host it is support for Python CGI - no SQL db or other nonsense required. The current functionality allows you to then use it as a custom auto post script with Mochi Media (a SF-based company offering over 15,000 flash games), meaning that once it's set up you can basically just explore and pick and choose from Mochi's game catalog, adding games to your site with a single click.
When the post request is made to the script, it does two main things. It first fetches the complete game feed and information from Mochi using Python Mochi. It then creates a page to display the game (example) and updates the index of your site with a thumbnail linking to that game page.
The site-making portion of the script is also capable of being run independently of adding a new game, in which case it checks your entire game library with the current Mochi repository and updates any games that are out of date. You can again run it from your browser using Python CGI, or you can execute the update directly from the command line (or cron it for convenience).
And that's it really - there's a healthy number of todos and known issues, but I hope this script is useful to others regardless. The main todo is making an admin interface of some sort that facilitates customization (at the moment you have to specify publish ID and other site aspects by editing the code - it's easy, but I suppose will still intimidate some). The main known issue is that not absolutely every Mochi game works - certain older games seem to not have the same sort of game_tag or otherwise fail with the Python Mochi package I am using.
But despite those caveats, I at least found this a fun and useful experience and hope others can as well. If nothing else, it's the only "flash web game arcade" script I'm aware of that is *not* written in PHP - which in my book is an excellent thing. In fact, the preponderance of PHP was the main reason I chose to write this at all, as I wanted something I could easily understand and customize. Python CGI turned out to be a very straightforward and pleasant experience, and I would suggest it for anyone looking to make a quick and simple "web app."
Subscribe to:
Posts (Atom)