• Quick note - the problem with Youtube videos not embedding on the forum appears to have been fixed, thanks to ZiprHead. If you do still see problems let me know.

Turing Computer

sorgoth

Muse
S
Joined
Aug 9, 2002
Messages
977
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?
 
sorgoth said:
What makes the 1's and 0's?
Click to expand...
The answer to every question you may have and more: God. :D



The little 1s and 0s are switches which mean "on" and "off". Current only flows through an "on" switch...

And I've exhausted my knowledge of computer hardware...
 
The 1s and 0s are logic gates in an on or off state. The logic gates are a few transistors wired together, that can lock into one of two stable states, and flip when required. Basically, just like an on/off switch on a lamp.

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.
 
Someone once built a computer that used water. See the 4th program in this link
 
ceptimus said:
The 1s and 0s are logic gates in an on or off state. The logic gates are a few transistors wired together, that can lock into one of two stable states, and flip when required. Basically, just like an on/off switch on a lamp.

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.
Click to expand...

And such a computer, if it were complex enough, would be conscious?
 
Originally posted by Yahweh

The little 1s and 0s are switches which mean "on" and "off". Current only flows through an "on" switch...
Click to expand...
Actually, even the "off" is on, just not as much; the two different states are two different voltages, a higher and a lower.
 
Of course you could go quantum
 
sorgoth said:
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?
Click to expand...

I haven't made one out of toilet paper rolls. But when I was a kid, I did make some digital stuff out of dominoes.
 
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.
 
LW said:
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.
Click to expand...

Is it not the case that in principle a Turing machine would be able to solve any problem which can be solved algorithmically?

And are you suggesting there are problems which cannot be solved algorithmically?
 
Interesting Ian:
Is it not the case that in principle a Turing machine would be able to solve any problem which can be solved algorithmically?

And are you suggesting there are problems which cannot be solved algorithmically?
Click to expand...
The problem is whether or not an algorithm halts.

From Wikipedia:
The halting problem is a decision problem which can be informally stated as follows:

Given a description of an algorithm and a description of its initial arguments, determine whether the algorithm, when executed with these arguments, ever halts (the alternative is that it runs forever without halting).

Alan Turing proved in 1936 that there is no general method or algorithm which can solve the halting problem for all possible inputs.

The importance of the halting problem lies in the fact that it was the first problem to be proved undecidable. Subsequently, many other such problems have been described; the typical method of proving a problem to be undecidable is to reduce it to the halting problem.
Click to expand...
 
Originally posted by Interesting Ian

And are you suggesting there are problems which cannot be solved algorithmically?
Click to expand...
There are problems which cannot be solved, period.

Originally posted by DanishDynamite

The problem is whether or not an algorithm halts...

...the typical method of proving a problem to be undecidable is to reduce it to the halting problem.
Click to expand...
It gets worse. Some problems may be undecidable, but this fact about them may be undecidable as well.
When an algorithm is put in motion, several things may occur. It may halt with a solution. It may halt with a negation of a solution (proof that no solution exists). It may fall into a repetitive loop, (proof that it will never produce a solution). Or it may continue to run on and on, never repeating, but never producing a solution (or negation) either. Let it run for a trillion years, and you still haven't proven that a solution does not exist; i.e., that next week or next year or next century, it will halt with a solution.
 
Dymanic said:
It gets worse. Some problems may be undecidable, but this fact about them may be undecidable as well.
Click to expand...
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. Perhaps I'm confused.
 
Originally posted by Iconoclast

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. Perhaps I'm confused.
Click to expand...
No, you're right; my statement was badly worded. Decidability is, a priori, undecidable; in fact, it doesn't even matter whether the problem is solvable or not.

So you have a Turing machine that attacks the problem, and another that looks at the first, trying to decide whether or not it will ever halt. What Turing showed is that no general algorithm can exist for the second Turing machine.
 
LW said:
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.
Click to expand...

The dice are for keeping track of your state
 
You must log in or register to reply here.

Back
Top Bottom