Oct 1, 2008

Models of Computation

A random thought: currently our idea of computability revolves around the idea that a Turing machine can be created to accept or reject the input (you can also use lambda or predicate calculus, but for the purposes of this blog entry I will ignore them). For example, I can create a Turing machine to calculate the square of a number. But I cannot create a Turing machine that takes as an input another Turing machine t and an arbitrary input x and say if t will halt on x or not.

A question: Given a computable problem P, is it possible to have a Turing machine that will output a Turing machine that solves P? In English, can we make a computer program that is a programmer?

A brain can do this. A brain (IMHO) is an advanced device that can compute things. If a brain can do it, can a Turing machine? If not, perhaps there is a more powerful computational automaton than a Turing machine, just as a Turing machine is more powerful than a push-down automaton, which in turn is more powerful than a finite-state automaton?

Thinking about this kind of thing makes me want to go back to school.

3 comments:

Chess Instructor said...

Hi Rob!
You wrote that you were working on pornhub project.
We need a script similar to that of that site.
Can you do that kind of work?
Val
val_2782 yahoo.com

Guillaume Theoret said...

hahaha that's a hilarious comment. That site was the result of at least a year of work by 3-4 programmers.

So, factor in a decent salary of say 50k are you really to pay 200k for the site? If not, don't expect something as good.

Rob Britton said...

Nah it wasn't a year, less than that. But yeah the costs are probably higher, considering you're not going to be making money for a while, and bandwidth costs are high for video streaming.