# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Courk
Daedalian Member

 Posted: Sat Jun 23, 2012 5:16 pm    Post subject: 1 Google's home page today has to do with Alan Turing, a man I had never heard of. I did enjoy the little puzzle game, though, and looked up Turing machine on Wikipedia. The explanation was much further in depth than I wanted or could even understand, so I'm hoping someone can give me a basic answer on what this sort of machine is for, and where I can find more puzzles like that.
Zag
Unintentionally offensive old coot

Posted: Sat Jun 23, 2012 6:00 pm    Post subject: 2

The concept of a "Turing Machine" is his proof that any sort of computer can be constructed just from some extremely basic parts: the ability to do boolean AND, OR, and NOT; to store and retrieve data; to perform instructions sequentially; and to compare and branch. Everything else is just repeated applications of those steps.

 aside wrote: For instance, addition is just a repeated sequence of AND's, OR's, and NOT's. (Consider adding two boolean values, A + B. The result is a two-digit boolean number XY, where X = A AND B, and Y = ((A OR B) AND NOT (A AND B)).

Turing further posited that the human brain is just an extremely complex computer, so it should be possible to simulate it, and thus was born the field of artificial intelligence. To the naysayers he suggested the experiment which became known as the "Turing Test." He said that if you were communicating with another being through a typing device, and after a long conversation you could not tell whether or not that was a human on the other side or a computer, then you have to admit that the computer is "intelligent" just as a human is. After all, what other evidence do you have of another human's intelligence other than his ability to communicate to you?
_________________
 Death Mage wrote: I couldn't agree with you more, Zag.
Courk
Daedalian Member

Posted: Sat Jun 23, 2012 6:54 pm    Post subject: 3

 aside wrote: For instance, addition is just a repeated sequence of AND's, OR's, and NOT's. (Consider adding two boolean values, A + B. The result is a two-digit boolean number XY, where X = A AND B, and Y = ((A OR B) AND NOT (A AND B)).

Can you walk me through this using actual numbers?
raekuul
Lives under a bridge & tells stories.

Posted: Sat Jun 23, 2012 7:00 pm    Post subject: 4

The best I've got to explain that aside is to try adding 4 and 5 using base 2 instead of base 10 (so, 100 + 101)

 Code: 100 +101 ____ 1001
Zag
Unintentionally offensive old coot

Posted: Sat Jun 23, 2012 7:52 pm    Post subject: 5

Courk wrote:
 aside wrote: For instance, addition is just a repeated sequence of AND's, OR's, and NOT's. (Consider adding two boolean values, A + B. The result is a two-digit boolean number XY, where X = A AND B, and Y = ((A OR B) AND NOT (A AND B)).

Can you walk me through this using actual numbers?

By 'boolean values' I meant literally a single bit, only 0 or 1. So, for boolean values A and B, there are only 4 combinations:

A = 0, B = 0. A+B = 00 (in binary, which is the decimal number 0)
A = 0, B = 1. A+B = 01 (in binary, which is the decimal number 1)
A = 1, B = 0. A+B = 01 (in binary, which is the decimal number 1)
A = 1, B = 1. A+B = 10 (in binary, which is the decimal number 2)

This is a half-adder. The lower bit is called the sum and the higher bit is the carry, because it will carry to the next column. Exactly as you would if you were adding decimal numbers, you get a digit in that column plus a value that carries to the next one.

Half-adders are put together to make a full adder. Each full adder adds its two bits, plus a carry from the previous column.

And these are cascaded to make a complete "add" operation that can add two numbers of 8, 16, 32, or 64 bits each.

All of this is just to add two 4-bit numbers!

(Ok, they don't really make cascades like this. The problem is that this approach only allows you to calculate one bit at a time, and you need the carry from it to calculate the next bit, and you need the carry from it to calculate the next one. For a fast computer, you don't really want to wait for a 64-level cascade just to do a simple add. So they actually have a much more complicated circuit that does all 64 bits at once. But that complicated circuit was made by working out the cascading circuit, then short-cutting all the cascading.

This is how computers really are designed, with lots and lots of AND, OR, and NOT gates. For every single tiny operation that a computer can do, there are thousands or millions of these gates, and some poor schlep (Antrax, maybe) designed them gate by gate, at one point.
_________________
 Death Mage wrote: I couldn't agree with you more, Zag.
Courk
Daedalian Member

 Posted: Sat Jun 23, 2012 8:19 pm    Post subject: 6 I still have several questions, but I'm not quite sure how to phrase them. I'll try forming a rational thought later.
Courk
Daedalian Member

Posted: Sat Jun 23, 2012 9:57 pm    Post subject: 7

 Code: -------------------------------------    |                                   | A--|----o----\ D                       |    |    |    |\_________________|--\   |    |  +-|----|/                 |&2 )--|--S    |  | |    /        |\ E   +--|--/   |    |  | |          +--| >o---+         |    |  | +---|--\   |  |/               | B--|--o-----|&1 )--o-------------------|--C    |        |--/                       |    |                                   |    -------------------------------------

So for 1+1, what goes on?

One of the 1s goes in along the A line (since A is a 1), gets to the Or gate, then what? Does that dot before the Or gate mean it "splits" and goes to both? So it's also heading to the leftmost And gate (labeled &1)? Same with the 1 represented by B? What I can gather from wikipedia, since A's a 1, the Or gate recognizes that, yes, it's a 1, so it outputs a 1 heading to the rightmost And gate (labeled &2)?
Meanwhile the other 1 goes in B and makes it to the And gate &1 and also splits off to the Or gate? So the B 1 when it gets to the or gate is also a 1, so that gate again says, yes, it's a 1, and outputs a 1? So since either A or B were a 1, the output there is a 1. For an Or, the A could be a 1, the B could be a 1, or both could be a 1, just so long as one of them is a 1, it'll output a 1?

So back to the first and gate, &1. A and B had split off upon entering this whole gate complex, so both are heading to the And gate. Both A *and* B are 1, so this gate will output a 1, whereas if A was a 0 or B was a 0, it would have said no, and output a 0.

So the 1 that's output from the or gate travels to the second and gate, and the 1 from the first and gate is going toward another split point, where one path lets it exit this gate complex as a 1, and the other sends it to the inverter (also a not gate, right?) This gate is asking if it's NOT a 1, which is a "No" since it *is* a 1, yielding an output of 0 (or the 1 was transmorgified into a 0). Now we have a 0 and a 1 going to the second and gate, at this gate, asking if these two numbers are the same, gets the result of 0, since no, it's now a 1 and a 0. So S (sum) is a 0, C (Carry) is a 1. THe carry carries to the next columnm yielding 10, a binary 2!

Is that right, or did I just happen upon the answer?

 Code: -------------------------------------    |                                   | 1--|----o---1\ D                       |    |    |    |\_1______________1|--\   |    |  +-|---1|/                 |&2 )-0|--0    |  | |    /        |\ E   +-0|--/   |    |  | |          +-1| >o-0-+         |    |  | +--1|--\   |  |/               | 1--|--o----1|&1 )1-o-1----------------1|--1    |        |--/                       |    |                                   |    -------------------------------------

1+0:
 Code: -------------------------------------    |                                   | 1--|----o---1\ D                       |    |    |    |\_1______________1|--\   |    |  +-|---0|/                 |&2 )-1|--1    |  | |    /        |\ E   +-1|--/   |    |  | |          +-0| >o-1-+         |    |  | +--1|--\   |  |/               | 0--|--o----0|&1 )0-o-0----------------0|--0    |        |--/                       |    |                                   |    ------------------------------------- The sum is 1, the carry is 0, so nothing's carried over, the answer is 1

0+1:
 Code: -------------------------------------    |                                   | 0--|----o---0\ D                       |    |    |    |\_1______________1|--\   |    |  +-|---1|/                 |&2 )-1|--1    |  | |    /        |\ E   +-1|--/   |    |  | |          +-0| >o-1-+         |    |  | +--0|--\   |  |/               | 1--|--o----1|&1 )0-o-0----------------0|--0    |        |--/                       |    |                                   |    ------------------------------------- Same as above, the sum is 1, the carry is 0, the answer is 1

Hey!
Scurra
Daedalian Member

 Posted: Sat Jun 23, 2012 10:39 pm    Post subject: 8 Turing was that rare thing - a genuine genius. As has often been observed, there's a difference between seeing a clever idea and thinking "now why on earth didn't I think of that?" and seeing a clever idea and thinking "there is no way I would ever have thought of that." A genius specialises in the second type of idea._________________ still Quiz Olympiad champion. Must get a life. New definitions: COFFEE - someone who is coughed upon
Thok
Oh, foe, the cursed teeth!

 Posted: Sat Jun 23, 2012 10:46 pm    Post subject: 9 Clearly this thread was made by a computer. Sorry, Courk, but you've failed the Turing Test.
Chuck
Daedalian Member

 Posted: Sat Jun 23, 2012 11:56 pm    Post subject: 10 I wonder how well we'll do when future machine intelligence makes us take their Turing test.
ralphmerridew
Daedalian Member

 Posted: Sun Jun 24, 2012 2:43 am    Post subject: 11 Zag: That's not a Turing machine. A Turing machine consists of: 1) A tape, infinite to the right. Each unit space on the tape can hold one of N symbols. 2) Internal memory corresponding to one of M states. (One of those states is called "START"; another is called "STOP".) 3) A list of instructions. Each instruction is of the form: (symbol1) (state1) (symbol2) (state2) (direction), where symbol1 and symbol2 are each one of the N symbols, state1 and state2 are each one of the M states, and direction is "left", "right", or "stay". Each line means "If the current state is state1, and the current space on the tape holds symbol1, then change to state2, write symbol2 on the tape, and move the tape one space left / right / don't move the tape." A machine starts with the tape at the leftmost position, and in state "START". As long as the state isn't STOP, follow the appropriate instruction. One big discovery was that there was a particular program, called a "universal turing machine", which could take a tape, containing a description of a machine and input for that machine, and determine what would happen if that tape was ran on that machine. (Mostly. If the emulated machine would run forever on that input, the universal turing machine would generally run forever analyzing it.)
Zag
Unintentionally offensive old coot

Posted: Sun Jun 24, 2012 5:08 am    Post subject: 12

 Courk wrote: Hey!

Nice!

I know that way back in college (I graduated in 1984, so probably in late 82 or early 83) I designed an entire 8-bit computer this way, just from gates. It saddens me that I don't think that I could do it today, but I'm not as smart as I used to be.
_________________
 Death Mage wrote: I couldn't agree with you more, Zag.
extropalopakettle
No offense, but....

 Posted: Sun Jun 24, 2012 5:11 am    Post subject: 13 The importance of the Turing machine is that is a simple formal model of computation believed to correspond to the informal notion of an algorithm. That is, it is believed that if there is an algorithm to compute some mathematical function, then it can be computed with a Turing machine. Or in other words, "computable via some algorithm" and "computable via a Turing machine" are accepted as equivalent. (there are other formal models of computation which are provably equivalent to Turing machines)
Courk
Daedalian Member

Posted: Sun Jun 24, 2012 5:40 am    Post subject: 14

0+0:
 Code: -------------------------------------    |                                   | 0--|----o---0\ D                       |    |    |    |\_0______________0|--\   |    |  +-|---0|/                 |&2 )-0|--0    |  | |    /        |\ E   +-1|--/   |    |  | |          +-0| >o-1-+         |    |  | +--0|--\   |  |/               | 0--|--o----0|&1 )0-o-0----------------0|--0    |        |--/                       |    |                                   |    -------------------------------------

For 0+0, the Or gate yeilds a 0 because neither is a 1, correct? And the first And gate is a 0 because, despite them being the same, they're both 0, and they would have needed to both be 1s, right?
Zag
Unintentionally offensive old coot

Posted: Sun Jun 24, 2012 2:34 pm    Post subject: 15

 Courk wrote: For 0+0, the Or gate yeilds a 0 because neither is a 1, correct? And the first And gate is a 0 because, despite them being the same, they're both 0, and they would have needed to both be 1s, right?

Both right. Check out this site. The link there has every bit of boolean algebra that I remember, but that's because that is all you really need. The links along the top all lead to some very nice descriptions of the most important concepts, with excellent pictures. If you were to learn everything from those links, that's one full semester's worth of digital electronics 101.
_________________
 Death Mage wrote: I couldn't agree with you more, Zag.
extropalopakettle
No offense, but....

 Posted: Sun Jun 24, 2012 3:05 pm    Post subject: 16 But as ralphmerridew noted, that's not a Turing machine. Basically, an infinite tape marked off into sequential cells. The machine has a finite number of states (not counting what's written on the tape as part of the state), and moves back and forth along the tape. Wherever it is on the tape, it can read the symbol written in that cell (the symbols are drawn from a finite alphabet, such as '0' and '1' - and cells may also be blank), and it can erase or write a symbol. The exact operation of the machine is prescribed by a table of state transitions and actions of the form: If in state A, and reading symbol N on the tape, then write (overwrite) symbol M (or erase the current symbol), go into state B, and either mover left, right, or stay at the current cell on the tape. There is a special "halt" state at which the machine stops. So, one can (it's complicated) define a state transition table that will, for instance, take a tape with two numbers written on it, separated by a blank, and will erase them and replace them with the product of those two numbers. That would be a special purpose Turing machine to do multiplication. Of special interest is the "universal turing machine", which can be configured to take a tape containing a description of any other turing machine's state transition table, followed by whatever else you might put on the tape as input to that other turing machine, and will produce the same output that that other turing machine would produce. Such a universal turing machine is useful as a formal model of a general purpose computer, at least so far as what it is capable of computing. In actuality, it's more powerful than our real computers, as it has infinite storage, and counting the tape, can have an infinite number of states, whereas "real" computers are finite state machines. Also noteworthy is that the "halting problem" - how to configure a turing machine (or write an algorithm) to determine whether a universal turing machine will eventually halt (as opposed to keep running forever) given some initial input ... also noteworthy is that this "halting problem" was one of the first of many precisely defined mathematical functions demonstrated to not be computable (i.e. there is no algorithm to compute it). (when we say "there is no algorithm", we assume that the informal notion of "algorithm" actually corresponds to what can be done by a turing machine, or can be done in countless other models of computation shown to be equivalent to a turing machine - this equivalence is known as the "Church-Turing Thesis") (sorry if that was a bit long-winded)
extropalopakettle
No offense, but....

 Posted: Sun Jun 24, 2012 3:27 pm    Post subject: 17 http://www.youtube.com/watch?v=40DkJ9vt5CI Here's a cool example of a mechanical Turing machine, which uses a metal grid with ball bearings as its "tape". The obvious shortcoming is that to be a true Turing machine, the grid would need to be infinitely long. As the narrator points out, it need not even employ electricity, but could be powered by a steam engine - gears, pistons, levers - no electronics. Turing proposed the "Turing Test" in addressing the question of whether machines can think, as a way to deal with the ambiguity of what we mean by "think". He instead addressed the question of whether a computer could be programmed to imitate a human in conversation, well enough that a human judge could not reliably distinguish between the two. The interesting philosophical consideration is that if we concede that a modern electronic computer, properly programmed, might conceivably pass the Turing Test, and from this conclude that it can "think", or "understand" (or whatever other philosophically loaded terms one would wish to choose for sake of consideration), then we would have to also accept that a mechanical steam powered device such as depicted above can "think" and "understand" all that a human can.
extropalopakettle
No offense, but....

Posted: Sun Jun 24, 2012 4:06 pm    Post subject: 18

Here's a remarkably simple example of a universal turing machine:

From:
http://www.wolframscience.com/prizes/tm23/turingmachine.html
http://www.wolframscience.com/prizes/tm23/

What the image means:
The infinite tape has cells with three possible colors: orange, yellow, white.
The moving head has two states, indicated by the black symbol pointed up or down.

The image means:
1) If in the 'up' state at an orange cell, color it yellow and move left and stay in the 'up' state.
2) If in the 'up' state at a yellow cell, color it orange and move left and stay in the 'up' state.
3) If in the 'up' state at a white cell, color it yellow and move right and go into the 'down' state.
4) If in the 'down' state at an orange cell, color it white and move right and go into the 'up' state.
5) If in the 'down' state at a yellow cell, color it orange and move right and stay in the 'down' state.
6) If in the 'down' state at a white cell, color it orange and move left and go into the 'up' state.

So, if a computer can "think" or "understand", so can the above, given a tape with some appropriate initial coloring of its cells in orange yellow and white.

Note that the above has no "halt" state. The wolfram site notes:

 Quote: Does your Turing machine halt? No. Like most real computers, it doesn't have a halt state; it just keeps computing forever. "Results" can get "read off" when the machine "says" it's ready by exhibiting some predefined behavior.

So it's universal in that it can emulate any other machine which eventually halts on some (or maybe all) input by producing that machines output (or an encoding of it), then producing something which means "done", and then whatever happens after that doesn't matter.
extropalopakettle
No offense, but....

 Posted: Sun Jun 24, 2012 4:21 pm    Post subject: 19 Also note that for any computation that will eventually achieve its result (such as demonstrating it has human understanding), it will only have used a finite portion of the tape, thus an infinite tape is not really required.
extropalopakettle
No offense, but....

 Posted: Sun Jun 24, 2012 4:25 pm    Post subject: 20 I came to my desk to check weather.com, and walked away having posted all the above, and forgetting about the weather.
Scurra
Daedalian Member

Posted: Sun Jun 24, 2012 7:33 pm    Post subject: 21

 extropalopakettle wrote: The interesting philosophical consideration is that if we concede that a modern electronic computer, properly programmed, might conceivably pass the Turing Test, and from this conclude that it can "think", or "understand" (or whatever other philosophically loaded terms one would wish to choose for sake of consideration), then we would have to also accept that a mechanical steam powered device such as depicted above can "think" and "understand" all that a human can.
Actually, I don't think there's anything especially interesting about conceding the second point - it seems perfectly clear that if an electronic computer could "pass" the Turing Test then so could a mechanical one (albeit probably only by extension and not through physical reality.)
The philosophical question is surely whether "passing" the Turing Test would actually mean anything anyway, and whether that would lead inevitably to the conclusion that a computer which "passed" it could be considered to be thinking or not. After all, it does rather depend upon the definition of "thinking" (as you said, a philosophically loaded term anyway, which takes us back into realms which we've argued about on here enough times, surely? )
_________________
still Quiz Olympiad champion. Must get a life.
New definitions: COFFEE - someone who is coughed upon
novice
No harm. Pun intended!

 Posted: Sun Jun 24, 2012 7:41 pm    Post subject: 22 Arguably, Artificial Intelligence is not here, but the Turing Test can be passed easily enough. So it's not a good metric for artificial intelligence. http://en.wikipedia.org/wiki/Turing_test#ELIZA_and_PARRY
extropalopakettle
No offense, but....

Posted: Sun Jun 24, 2012 8:10 pm    Post subject: 23

 novice wrote: Arguably, Artificial Intelligence is not here, but the Turing Test can be passed easily enough. So it's not a good metric for artificial intelligence. http://en.wikipedia.org/wiki/Turing_test#ELIZA_and_PARRY

I don't think those demonstrate the Turing test being passed.

Eliza was never all that good, and anyone who knowingly sat down to distinguish it from a real person would easily succeed.

The parameters of the test with Parry aren't made clear there.

 Quote: A group of experienced psychiatrists analysed a combination of real patients and computers running PARRY through teleprinters. Another group of 33 psychiatrists were shown transcripts of the conversations. The two groups were then asked to identify which of the "patients" were human and which were computer programs.[3] The psychiatrists were able to make the correct identification only 48 percent of the time — a figure consistent with random guessing.

Did the first group know they were interacting with either real patients or a program, and that the result of their interaction was to be given to a second group to tell which were real, and which were machine, so that they would direct the conversation in ways to make the difference apparent?

I might easily accept a poorly counterfeited \$20 bill that, if it were handed to me along with a real 20, and I were told one is fake, one real, I would easily identify as the fake.

To me, a valid Turing test means textual conversation with a person and with a machine, knowing one is a person, one a machine, and being allowed to guide the conversation with the aim of telling one from the other. I think if that test is passed, and one can't discern which is which, then a kind of functional intelligence is clearly demonstrated.
extropalopakettle
No offense, but....

 Posted: Sun Jun 24, 2012 8:15 pm    Post subject: 24 And not to mention that with Parry, we're testing schizophrenics (not mentally healthy humans) against simulations.
extropalopakettle
No offense, but....

Posted: Sun Jun 24, 2012 8:20 pm    Post subject: 25

 extropalopakettle wrote: So, one can (it's complicated) define a state transition table that will, for instance, take a tape with two numbers written on it, separated by a blank, and will erase them and replace them with the product of those two numbers. That would be a special purpose Turing machine to do multiplication.

There's a Turing machine simulator here: http://morphett.info/turing/turing.html where you can do just that. There's a drop-down list of example programs, one being binary multiplication. You can load the program, set the initial contents of the tape, and run it.
novice
No harm. Pun intended!

Posted: Sun Jun 24, 2012 8:33 pm    Post subject: 26

 extropalopakettle wrote: To me, a valid Turing test means textual conversation with a person and with a machine, knowing one is a person, one a machine, and being allowed to guide the conversation with the aim of telling one from the other. I think if that test is passed, and one can't discern which is which, then a kind of functional intelligence is clearly demonstrated.

Yeah, I agree with this. In popular science, the Turing Test is often described more loosely than this - too loosely.

There are probably aspects of human intelligence that are hard to verify using this version of a Turing Test too, though.
extropalopakettle
No offense, but....

Posted: Sun Jun 24, 2012 11:16 pm    Post subject: 27

extropalopakettle wrote:
 extropalopakettle wrote: So, one can (it's complicated) define a state transition table that will, for instance, take a tape with two numbers written on it, separated by a blank, and will erase them and replace them with the product of those two numbers. That would be a special purpose Turing machine to do multiplication.

There's a Turing machine simulator here: http://morphett.info/turing/turing.html where you can do just that. There's a drop-down list of example programs, one being binary multiplication. You can load the program, set the initial contents of the tape, and run it.

For that simulator, here's the script for the simple universal machine on the wolfram site:

0 O Y l 0
0 Y O l 0
0 _ Y r 1
1 O _ r 0
1 Y O r 1
1 _ O l 0

; \$INITIAL_TAPE: _
Jedo the Jedi
Paragon in Training

Posted: Mon Jun 25, 2012 2:57 am    Post subject: 28

 Chuck wrote: I wonder how well we'll do when future machine intelligence makes us take their Turing test.

These type of comments from Chuck tell me he either really is a computer or he's the crazy old hermit living in the cave who helps save humanity.What if he's both?!
_________________
Paragon Tally: 19 mafia, 3 SKs (1 twice), 1 cultist, numerous chat scum...and counting.
Nsof
Daedalian Member

 Posted: Tue Jun 26, 2012 1:22 pm    Post subject: 29 @Courk If you liked the google doodle then this was posted by Jack_Ian. There are few posts with hidden solutions later on. If you liked the theory behind turing machines then there are several followup "turing machine"-like concepts that I and others can suggest_________________Will sell this place for beer
Zag
Unintentionally offensive old coot

Posted: Thu Jul 19, 2012 2:44 pm    Post subject: 30

Totally worth watching! SciShow's tribute to Alan Turing.

This is the short form:

_________________
 Death Mage wrote: I couldn't agree with you more, Zag.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersChuckCourkextropalopakettleJedo the JedinoviceNsofraekuulralphmerridewScurraThokZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum