Turing Computer

[Iconoclast]

Dymanic, what you're saying is that decidability in the general case is undecidable. Right?

No, only undecideability in undecideable. If an algorithmic problem is solvable then we can prove it by solving it. If it's unsolvable then we have no way of knowing whether or not it can be solved.

So, all previously solved problems are solvable, all unsolved problems have indeterminate solvability.

[edited to add:]

Simon Singh in "Fermat's Last Theorem" mentions that a mathematician's worst nightmare is the possibility of spending a dozen or so years working on an unsolvable problem.

 

[Dymanic]

Originally posted by Iconoclast

If an algorithmic problem is solvable then we can prove it by solving it.

Right. What we can't do is establish its solvablity without solving it.

So let's say we have some statement about numbers, like: "Every odd integer may be expressed as the sum of two even integers". To test this statement, we program a Turing machine to test integers incrementally, stopping if it finds an example which contradicts the statement we are testing. It so happens that this particular Turing machine will halt almost before it gets started, solving the problem by providing a counterexample.

Now what would be slick and cool would be if we could program a second Turing to examine the first, and tell us whether it will halt -- but without actually tackling the problem itself (after all, what would be the point of that?) The answer to this does just as good a job of answering the original question, and for precisely this reason (as Turing showed) no such general algorithm can exist.

It's the same whether the problem is solvable or not. Such a (second) Turing machine is making a statement about numbers.

 

[RussDill]

Right. What we can't do is establish its solvablity without solving it.

So let's say we have some statement about numbers, like: "Every odd integer may be expressed as the sum of two even integers". To test this statement, we program a Turing machine to test integers incrementally, stopping if it finds an example which contradicts the statement we are testing. It so happens that this particular Turing machine will halt almost before it gets started, solving the problem by providing a counterexample.

no we don't. If you want to prove that is a problem is solvable, one way of doing it is to solve it with another problem that is solveable. However, with a math problem like that, we'd replace odd number with the term (2n + 1) and even number with the term 2n (placing valid limits on n). I'd be impossible to test every instance. However, with this example, no work is really necessary because 1 is odd, and there are no even numbers less than or equal to 1 (unless you want to go into negative numbers)

 

[Yahweh]

And such a computer, if it were complex enough, would be conscious?

I'd say a safe estimate for the first conscious computers would be a good 200 - 300 years away...

I've heard with the speed computers are advancing, it shouldnt be much more than 50 years, I'm a bit skeptical of a figure that low...

 

[Dymanic]

Originally posted by RussDill

no we don't.

Well, right. Ok. No kiddin.

But let's say we do that, for the purpose of illustrating the consequences of the halting problem (rather than solving the intentionally trivial problem I posed as a toy example.)

It'd be impossible to test every instance.

That's exactly why an algorithm that could test the algorithm that attacks the problem would be such a handy thing to have.

Say the problem was a bit tougher -- establishing the truth or falsehood of the statement:

"The equation, aⁿ + bⁿ = cⁿ has no solutions for which n > 2".

Again, creating an algorithm to test sequential integer values, halting if a solution was found, would be trivial...and relatively useless, since its failure to terminate would not stand as a proof that it could not terminate, no matter how many values you tested. But an algorithm which, by testing that algorithm, could determine whether it would halt would, by implication, serve as a proof.

 

[EdipisReks]

I'd say a safe estimate for the first conscious computers would be a good 200 - 300 years away...

I've heard with the speed computers are advancing, it shouldnt be much more than 50 years, I'm a bit skeptical of a figure that low...

do some reading about the singularity, especially Kurzweil's AI work. it might change your mind. www.kurzweilai.net is a good starting point.

 

[LW]

I thought Turing proved than an unsolvable problem necessarily can't be shown to be unsolvable a priori, that is to say, if a problem cannot be solved then it also cannot (ever) be shown to be unsolvable.

There is a really large number of problems that can be proved to be unsolvable.

One of the most important result in computability analysis is Rice's Theorem that establishes that every non-trivial problem about computations of Turing machines is undecidable. (A problem is trivial if the answer is the same for all Turing machines).

What this means in practice is that if there is some question about behavior of computer programs, then finding the answer for it is impossible in the general case.

One important thing to remember is that even if a problem is undecidable, it doesn't mean that all instances of it are impossible to solve. There may be infinite number of special cases where it actually can be solved. For example, if there is a computer program that does nothing but exit, then we certainly can know that it halts even though the halting problem is undecidable.

 

[sorgoth]

A Turing machine is perhaps the simplest formal model of computation that captures the whole class of computable functions. That is, everything that you can do on a computer could be done using a Turing machine.

A Turing machine consists of a set of states, an input tape, and a read/write head that points at some position of the tape. For each combination of state and input symbol there is a rule stating what the machine should do if it is in the state and the read/write head is looking at the symbol. In every computation step the machine:

- looks what state it is in;
- looks what symbol it is looking at; and then based on the transition rules it
- moves into a new state;
- writes a new symbol to the input tape; and
- possibly moves its read/write head one step to left or right.

This is a very simple model of computation, but thus far no-one has managed to find a problem that can be solved algorithmically but cannot be solved by a Turing machine.

If one wants to run a Turing machine by hand, then toilet paper can be used as the input tape. However, dice don't have anything to do with standard Turing machines, probabilistic Turing machines are an altogether different beast.

Edited after reading it over a few times: So what are the transition rules? What 'tells' it that this rule is so and so, and if not, it's so and so? Or does the symbol itself contain the information needed to move on to the next state?

 

[Dymanic]

Originally posted by sorgoth

So what are the transition rules? What 'tells' it that this rule is so and so, and if not, it's so and so?

That is what is called the Turing machine's specification, predetermined by its designer.

example

What is important to understand is that 'machine' here refers to an abstract, theoretical machine, rather than an actual physical machine. Using heads and tails in a row of coins also makes a convenient way to represent a two-output state Turning machine.

 

[iSani]

In principle you could make a computer out of mechanical things - balls rolling along tubes, clockwork, that kind of thing. It could run just the same programs as your PC does, but would be a LOT bigger, and a LOT slower.

Indeed, any Turing machine can run the same algorithms - given sufficient memory and time. It doesn't matter whether the machine is built out of transistors or paper clips and mouse traps. If memory is infinite, all programs will run. (At some speed, anyway.)

In the real world, then, memory and available time are the limiting factors for what a computer can process. A mechanical computer would have to be truly enormous, to store the megabytes of memory needed for typical PC programs.

 

[DanishDynamite]

I seem to recall reading about a rope-and-pulley computer several years ago in Scientific American. I did a little googling and came up with a hit, albeit not related to SciAm.

The Rope-and-Pulley Wonder

An excerpt:

On the island of Apraphul off the northwest coast of New Guinea, archaeologists have discovered the rotting remnants of an ingenious arrangement of ropes and pulleys thought to be the first working digital computer ever constructed. Chief investigator Robert L. Ripley of the Charles Fort College in New York dates the construction to approximately A.D. 850.

....

The ancient rope-and-pulley computer has been partially reconstructed by Ripley and his team at the Tropical Museum of Marine Antiquities in nearby Sumatra. Scouring a site that extends through several kilometres of dense jungle east of the Pulleg Mountains, the group found faint traces of buried jute fibres and noted the exact position of badly corroded brass pulleys and associated hardware. The reconstruction has given me an ideal opportunity to introduce readers to the principles of digital computing without resorting to tiny and mysterious electronic components. Here are gates, flip-flops, and circuits made entirely of rope and pulleys. It is all visible and perfectly easy to understand.

 

[Brown]

I believe one of Martin Gardner's "Mathematical Games" columns describes a techinque for building a Turing computer with adding machine tape. Sorry, I don't have a book or magazine reference for his column.

Neither do I have a reference for what I'm about to say, but I once saw a book describe how to solve (at least in principle) an extremely complicated calculus problem using an adding machine tape computer.

 

[Paul C. Anagnostopoulos]

Iconoclast said:

No, only undecideability in undecideable. If an algorithmic problem is solvable then we can prove it by solving it. If it's unsolvable then we have no way of knowing whether or not it can be solved.

Are we confusing undecidable and unsolvable here? I think you mean "If it's undecidable then we have no way of knowing whether or not it can be solved." And I'm not sure what your first sentence means. There are certainly problems that are provably undecidable.

~~ Paul

 

[sorgoth]

I seem to recall reading about a rope-and-pulley computer several years ago in Scientific American. I did a little googling and came up with a hit, albeit not related to SciAm.

The Rope-and-Pulley Wonder

An excerpt:

Interesting. So, in theory, if I connected each group of ropes to a light (RGB), and had a LOT of power handy, you could run a computer game on it. Heh.

 

[ceptimus]

So let's say we have some statement about numbers, like: "Every odd integer may be expressed as the sum of two even integers".

That's a poor example, as it is obviously false. The sum of two even integers is always even.

I think the one you were thinking about is the Goldbach's conjecture: Every even number is the sum of two primes.

 

[69dodge]

Originally posted by sorgoth
I read in Steven Pinker's How the Mind Works that Alan Turing said that one could, theoretically, build a computer out of dice, toilet paper rolls and other stuff. How?

Or, perhaps more to the point, how does a computer work at the very bottom rung? What makes the 1's and 0's?

The point of the comment about toilet paper rolls is precisely that the details are not especially important. The idea of a Turing machine is applicable to any real computer regardless of what its 1s and 0s happen to be made of.

 

[ceptimus]

And such a computer, if it were complex enough, would be conscious?

Yes - I think it would.

Edit: I'll add a bit of detail to that. I think 'consciousness' is a label that we apply to the actions of sufficiently complex machines (only brains fit the description, 'sufficiently complex' at the time of writing).

I think that brains obey the laws of physics. I think there may be some laws of physics, still undiscovered, that might have a bearing on brain operation. I believe all laws of physics, including as-yet-undiscovered ones could be modelled by a sufficiently complex computer, including a mechanical one.

There is one rider on this - the mechanical computer might be so slow in it's action, that we could not see it's consciousness. If we asked it a question, 'Are you conscious?' for example, and it took three hundred years to reply, we would get tired of waiting. In principle, you could use time lapse photography to compress the time scale. Our descendants might watch such a film in the future, seeing several thousand years worth of action compressed into two minutes or so, and agree that the mechanical marvel did indeed display all the signs of consciousness

 

[Peter Soderqvist]

Right. What we can't do is establish its solvablity without solving it.

So let's say we have some statement about numbers, like: "Every odd integer may be expressed as the sum of two even integers". To test this statement, we program a Turing machine to test integers incrementally, stopping if it finds an example which contradicts the statement we are testing. It so happens that this particular Turing machine will halt almost before it gets started, solving the problem by providing a counterexample.

Soderqvist1: Yes, the first Turing machine will halt at 2 + 3 = 5 since this formula has disproved that "Every odd integer may be expressed as the sum of two even integers".

Now what would be slick and cool would be if we could program a second Turing to examine the first, and tell us whether it will halt -- but without actually tackling the problem itself (after all, what would be the point of that?) The answer to this does just as good a job of answering the original question, and for precisely this reason (as Turing showed) no such general algorithm can exist.

It's the same whether the problem is solvable or not. Such a (second) Turing machine is making a statement about numbers.

Soderqvist1: what do you really mean here?
As far as I have understood; some particular algorithm can tell when some particular Turing machine will halt, but there is no universal algorithm, which can tell us if a Turing machine will halt, or not regarding every possible computation, Goldbach 's conjecture is one formally undecidable statement! Goldbach's conjecture is a truth mathematical statement, because there is no counterexample, but still unprovable because Goldbach's conjecture have no theorem!

 

[Dymanic]

Originally posted by ceptimus

So let's say we have some statement about numbers, like: "Every odd integer may be expressed as the sum of two even integers".

--------------------------------------------------------------------------------

That's a poor example, as it is obviously false. The sum of two even integers is always even.

It wasn't a mistake. I chose that example precisely because it is obviously false.

Originally posted by Soderqvist1

what do you really mean here?

What I mean is that there is no way to 'beat the system' and avoid the nuisance of actually working with the numbers themselves by working instead with the algorithms that do.

 

[SFB]

I seem to recall reading about a rope-and-pulley computer several years ago in Scientific American. I did a little googling and came up with a hit, albeit not related to SciAm.

The Rope-and-Pulley Wonder

An excerpt:

Very interesting site DD. Though not digital in nature, the abacus, often considered the first computer, still predates the rope and pulley device.

The abacus was mentioned in a Chinese piece of literature dated 190 CE.

http://inventors.about.com/gi/dynam....chinavista.com/experience/abacus/abacus.html