Creatures is eating my brain.

"Predictor" <predictr.TakeThisOut@bellatlantic.net> wrote in message
news:1108690693.823094.106240@c13g2000cwb.googlegroups.com...
> nornagon wrote:
>> But yes, Turing machines can, by definition, do anything.
>
>
> Can a Turing machine make a bowl of soup? Can it walk a dog? More
> importantly, can a Turing machine solve the Halting Problem?
>
>
> -Will Dwinnell
> http://will.dwinnell.com
>

What was that quote from either Steve or Toby about throwing Deep Blue into
the water... That with all it's AI it would still sink.

Don
AmberCreatures
http://creatures.amberz.net
 >> Stay informed about: Creatures is eating my brain. 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

Vadim wrote:
| Predictor wrote:
|
|
|>>nornagon wrote:
|>>
|>>>But yes, Turing machines can, by definition, do anything.
|>>
|>>
|>>Can a Turing machine make a bowl of soup? Can it walk a dog?
|
| Of course it can!
|
| It could make a virtual bowl of soup or walk a virtual dog inside
| the world it simulates.
|
| I mean, we all play Creatures games here
|
|
|>>More importantly, can a Turing machine solve the Halting
|>>Problem?
|
| Nothing can solve the halting problem. For example, does a
| program that search for this post in Pi halt? We don't know.
| It's perfectly possible that this post doesn't even happen in
| the infinity of Pi. Or maybe it does.

IIRC, wasn't it proven that it does?

Better to use the original proof (paraphrased):

Let H(p,i) be a function which takes as input the strings p and i and
returns a boolean value indicating whether running the program
represented by p with input i halts.

Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
returns false.

Since all algorithms can be represented by strings, T must have such a
string. Call it t.

What is T(t)?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCFpixek8FNvG1IuYRAyiwAJ9dkw4VE/cqSYAbMktALJfAoJ0gaQCfe0yi
IXCOOmDtEYyF1qnXupLUuL8=
=s6ig
-----END PGP SIGNATURE-----
 >> Stay informed about: Creatures is eating my brain. 

-----BEGIN PGP SIGNED MESSAGE-----

bd wrote:
| Vadim wrote:
| | Predictor wrote:
| |
| |
| |>>nornagon wrote:
| |>>
| |>>>But yes, Turing machines can, by definition, do anything.
| |>>
| |>>
| |>>Can a Turing machine make a bowl of soup? Can it walk a dog?
| |
| | Of course it can!
| |
| | It could make a virtual bowl of soup or walk a virtual dog inside
| | the world it simulates.
| |
| | I mean, we all play Creatures games here
| |
| |
| |>>More importantly, can a Turing machine solve the Halting
| |>>Problem?
| |
| | Nothing can solve the halting problem. For example, does a
| | program that search for this post in Pi halt? We don't know.
| | It's perfectly possible that this post doesn't even happen in
| | the infinity of Pi. Or maybe it does.
|
| IIRC, wasn't it proven that it does?
|
| Better to use the original proof (paraphrased):
|
| Let H(p,i) be a function which takes as input the strings p and i and
| returns a boolean value indicating whether running the program
| represented by p with input i halts.
|
| Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
| returns false.
|
| Since all algorithms can be represented by strings, T must have such a
| string. Call it t.
|
| What is T(t)?

Now you have to proof that t>t, but I am tired

Thomas
- --
"All my life, I've always wondered, What it would be like to fire a
ballistic missile" - Wonderfully colored plastic war toys, The Dead
Milkmen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQB5AwUBQhiEXAEP2l8iXKAJAQFBkQMfWe75Xj61mTyErZxg71JqiZKLpFnh0Dxc
ijPKIRo1MLywvP/wIZAw4su9sxhAw7e6vNzq56Z/G2zeb6UvITDA9ZCNPg6rVwYX
tOlyEsVmAb1Kx+QF3VYOH191NAyy9EWf5vPrwQ==
=E0Km
-----END PGP SIGNATURE-----
 >> Stay informed about: Creatures is eating my brain. 

On 2005-02-18, Don <admin RemoveThis @amberz.nospam.net> wrote:
>
> "Predictor" <predictr RemoveThis @bellatlantic.net> wrote in message
> news:1108690693.823094.106240@c13g2000cwb.googlegroups.com...
>> nornagon wrote:
>>> But yes, Turing machines can, by definition, do anything.
>>
>>
>> Can a Turing machine make a bowl of soup? Can it walk a dog? More
>> importantly, can a Turing machine solve the Halting Problem?
>>
>>
>> -Will Dwinnell
>> http://will.dwinnell.com
>>
>
> What was that quote from either Steve or Toby about throwing Deep Blue into
> the water... That with all it's AI it would still sink.

Steve. It was a rabbit and Deep Blue.
--
emmel <the_emmel*you-know-what-that's-for*@gmx.net>
(Don't forget to remove the ** bit)

Official AGC feedback maniac

"God is playing creatures - and we're the norns."

"A hundred dead are a tragedy - a hundred thousand are statistics."

"I guess you can call yourself lucky." -
"I could, but Linda suits me a little better...
Things called lucky tend to get hit by trucks."

Hi, I'm a .sig virus. Just copy me to your .signature. And don't worry.
 >> Stay informed about: Creatures is eating my brain. 

"bd" <bdonlan.DeleteThis@bd.beginyourfear.com> wrote in message
news:eb7fe2-gc8.ln1@bd-home-comp.no-ip.org...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> The Triad wrote:
> | <snip>
> |
> |>>>(Did you know
> |>>>that Conway's Game of Life is Turing complete? Yep, someone built a
> |>>>Turing machine in Life.)
> |>>
> |>>Ooo. *blinks*
> |>>
> |>>...can it simulate another Turing machine running Half-Life?
> |>
> |>*groans and calls 1800-BADJOKE*
> |>
> |>But yes, Turing machines can, by definition, do anything.
> |
> |
> | Er, we were being serious. Is there some reason why this wouldn't be
> | feasible? (To make our particular curiosity somewhat clearer, we're
> also
> | wondering whether it would be possible to construct a Turing machine
> | entirely out of pings (or similar signals), without having to install
> | specialised software on all the computers/networking thingamajigs
> involved.)
>
> A universal turing machine (like a computer*) requires a program. If
> that program is another UTM, so be it. However, the program must still
> be present. In other words, yes, you'd need to arrange the proper
> emulation software on the UTMs involved.
>
> * - technically, a computer is not a turing machine, as it does not have
> infinite storage.

Hmm.

....patterns...

Once one fully understand how to do it, then in theory, it should be...
relatively simple to get started. The act, that is. The understanding
exactly /what/ to do would probably take quite a bit longer, most likely.

--
The Triad
User of 'Thingamajig!'
Refractor Dragon -=(UDIC)=-
 >> Stay informed about: Creatures is eating my brain. 

Thomas J. Boschloo InSaNiTised:

> -----BEGIN PGP SIGNED MESSAGE-----
>
> bd wrote:
> | Vadim wrote:
> | | Predictor wrote:
> | |
> | |
> | |>>nornagon wrote:
> | |>>
> | |>>>But yes, Turing machines can, by definition, do anything.
> | |>>
> | |>>
> | |>>Can a Turing machine make a bowl of soup? Can it walk a dog?
> | |
> | | Of course it can!
> | |
> | | It could make a virtual bowl of soup or walk a virtual dog inside
> | | the world it simulates.
> | |
> | | I mean, we all play Creatures games here
> | |
> | |
> | |>>More importantly, can a Turing machine solve the Halting
> | |>>Problem?
> | |
> | | Nothing can solve the halting problem. For example, does a
> | | program that search for this post in Pi halt? We don't know.
> | | It's perfectly possible that this post doesn't even happen in
> | | the infinity of Pi. Or maybe it does.
> |
> | IIRC, wasn't it proven that it does?
> |
> | Better to use the original proof (paraphrased):
> |
> | Let H(p,i) be a function which takes as input the strings p and i and
> | returns a boolean value indicating whether running the program
> | represented by p with input i halts.
> |
> | Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
> | returns false.
> |
> | Since all algorithms can be represented by strings, T must have such a
> | string. Call it t.
> |
> | What is T(t)?
>
> Now you have to proof that t>t, but I am tired
>

t can't be greater than t. O.o

--
- nornagon
http://www.nornrock.com
mailto: nornagon.TakeThisOut@gmail.com
DS Species range: 10001-10100
 >> Stay informed about: Creatures is eating my brain. 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

nornagon wrote:
| Thomas J. Boschloo InSaNiTised:
|
|
|>-----BEGIN PGP SIGNED MESSAGE-----
|>
|>bd wrote:
|>| Vadim wrote:
|>| | Predictor wrote:
|>| |
|>| |
|>| |>>nornagon wrote:
|>| |>>
|>| |>>>But yes, Turing machines can, by definition, do anything.
|>| |>>
|>| |>>
|>| |>>Can a Turing machine make a bowl of soup? Can it walk a dog?
|>| |
|>| | Of course it can!
|>| |
|>| | It could make a virtual bowl of soup or walk a virtual dog inside
|>| | the world it simulates.
|>| |
|>| | I mean, we all play Creatures games here
|>| |
|>| |
|>| |>>More importantly, can a Turing machine solve the Halting
|>| |>>Problem?
|>| |
|>| | Nothing can solve the halting problem. For example, does a
|>| | program that search for this post in Pi halt? We don't know.
|>| | It's perfectly possible that this post doesn't even happen in
|>| | the infinity of Pi. Or maybe it does.
|>|
|>| IIRC, wasn't it proven that it does?
|>|
|>| Better to use the original proof (paraphrased):
|>|
|>| Let H(p,i) be a function which takes as input the strings p and i and
|>| returns a boolean value indicating whether running the program
|>| represented by p with input i halts.
|>|
|>| Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
|>| returns false.
|>|
|>| Since all algorithms can be represented by strings, T must have such a
|>| string. Call it t.
|>|
|>| What is T(t)?
|>
|>Now you have to proof that t>t, but I am tired
|>
|
|
| t can't be greater than t. O.o
|

Reductio ad absurdum.
(sp?)

Anyway, it's not t>t, it's that T(t) is false if true, but true if
false. Therein lies the contradiction, proving there is no halting
algorithm.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQEVAwUBQhpZXvzMPsvJqdmPAQPzgQf+ITFNAUD42KROSmY1NlmnSE/7pGU+9uRe
XBgbtPkXk/wK7MLPSG30rqSXQU123dnl+wFj7+hv0zv/sEK/H6D/QCBz+LLflnMy
c/vixup5Npj+6nGwFencJK9nIPo1Dph877H70lKu9FgxVGg/jSdEd92UE4FnuW/p
hvAUM/AIhpRa48wVrLVjoqMtmYmaDHfSgWKKCIOyPV3/vgD/4kXwZMIXGe/fKM8j
WSfKNkXZ69Mms/XRjpwvZYBWalFx0UFjfTYQ+3DNEa9yU8RF785blT+TuWyUXQBz
/sSptN5W60yrNwYCitnG7Hyodp3y9N+lRCfm9M/FSXgNporqK/2p6g==
=Tq2m
-----END PGP SIGNATURE-----
 >> Stay informed about: Creatures is eating my brain. 

-----BEGIN PGP SIGNED MESSAGE-----

bd wrote:
> nornagon wrote:
> | Thomas J. Boschloo InSaNiTised:
> |
> |
> |>-----BEGIN PGP SIGNED MESSAGE-----
> |>
> |>bd wrote:
> |>| Vadim wrote:
> |>| | Predictor wrote:
> |>| |
> |>| |
> |>| |>>nornagon wrote:
> |>| |>>
> |>| |>>>But yes, Turing machines can, by definition, do anything.
> |>| |>>
> |>| |>>
> |>| |>>Can a Turing machine make a bowl of soup? Can it walk a dog?
> |>| |
> |>| | Of course it can!
> |>| |
> |>| | It could make a virtual bowl of soup or walk a virtual dog inside
> |>| | the world it simulates.
> |>| |
> |>| | I mean, we all play Creatures games here
> |>| |
> |>| |
> |>| |>>More importantly, can a Turing machine solve the Halting
> |>| |>>Problem?
> |>| |
> |>| | Nothing can solve the halting problem. For example, does a
> |>| | program that search for this post in Pi halt? We don't know.
> |>| | It's perfectly possible that this post doesn't even happen in
> |>| | the infinity of Pi. Or maybe it does.
> |>|
> |>| IIRC, wasn't it proven that it does?
> |>|
> |>| Better to use the original proof (paraphrased):
> |>|
> |>| Let H(p,i) be a function which takes as input the strings p and i and
> |>| returns a boolean value indicating whether running the program
> |>| represented by p with input i halts.
> |>|
> |>| Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
> |>| returns false.
> |>|
> |>| Since all algorithms can be represented by strings, T must have such a
> |>| string. Call it t.
> |>|
> |>| What is T(t)?
> |>
> |>Now you have to proof that t>t, but I am tired
> |>
> |
> |
> | t can't be greater than t. O.o
> |
>
> Reductio ad absurdum.
> (sp?)
>
> Anyway, it's not t>t, it's that T(t) is false if true, but true if
> false. Therein lies the contradiction, proving there is no halting
> algorithm.

I remember a proof where you would make a list of all possible programs
in an 2d array like:


01100101010
00101100101
11010111000
10011000110

etc.

Then you would prove there was one more 'program' on the turing machine
by taking the first bit from T(1), the second from T(2), etc. and then
reverse all those bits proving an additional program exists that you
didn't count at first.

But that was years ago for me (1996). I don't really remember the
details of what the proof was about but it seemed to me that you could
use something that like to proof that Pi is larger than the Pi you
calculated before.

Thomas
- --
"All my life, I've always wondered, What it would be like to fire a
ballistic missile" - Wonderfully colored plastic war toys, The Dead
Milkmen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQB5AwUBQiHaVAEP2l8iXKAJAQFDjAMfTQFHk1Y+2A+aZaRcDAiSxGoSjP9yRFiw
R2l9dL+CikVyLjsjAyKhv2W0sZcdxkTpJm0buHGRpGmuB5u+esy8ye7rwBCNynP3
MldCFThjiR0BnQuAoBhWIYGAST7zK7PHqgQpjw==
=WqT2
-----END PGP SIGNATURE-----
 >> Stay informed about: Creatures is eating my brain. 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

Thomas J. Boschloo wrote:
| bd wrote:
|
|>>nornagon wrote:
|>>| Thomas J. Boschloo InSaNiTised:
|>>|
|>>|
|>>|>-----BEGIN PGP SIGNED MESSAGE-----
|>>|>
|>>|>bd wrote:
|>>|>| Vadim wrote:
|>>|>| | Predictor wrote:
|>>|>| |
|>>|>| |
|>>|>| |>>nornagon wrote:
|>>|>| |>>
|>>|>| |>>>But yes, Turing machines can, by definition, do anything.
|>>|>| |>>
|>>|>| |>>
|>>|>| |>>Can a Turing machine make a bowl of soup? Can it walk a dog?
|>>|>| |
|>>|>| | Of course it can!
|>>|>| |
|>>|>| | It could make a virtual bowl of soup or walk a virtual dog inside
|>>|>| | the world it simulates.
|>>|>| |
|>>|>| | I mean, we all play Creatures games here
|>>|>| |
|>>|>| |
|>>|>| |>>More importantly, can a Turing machine solve the Halting
|>>|>| |>>Problem?
|>>|>| |
|>>|>| | Nothing can solve the halting problem. For example, does a
|>>|>| | program that search for this post in Pi halt? We don't know.
|>>|>| | It's perfectly possible that this post doesn't even happen in
|>>|>| | the infinity of Pi. Or maybe it does.
|>>|>|
|>>|>| IIRC, wasn't it proven that it does?
|>>|>|
|>>|>| Better to use the original proof (paraphrased):
|>>|>|
|>>|>| Let H(p,i) be a function which takes as input the strings p and i and
|>>|>| returns a boolean value indicating whether running the program
|>>|>| represented by p with input i halts.
|>>|>|
|>>|>| Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
|>>|>| returns false.
|>>|>|
|>>|>| Since all algorithms can be represented by strings, T must have
such a
|>>|>| string. Call it t.
|>>|>|
|>>|>| What is T(t)?
|>>|>
|>>|>Now you have to proof that t>t, but I am tired
|>>|>
|>>|
|>>|
|>>| t can't be greater than t. O.o
|>>|
|>>
|>>Reductio ad absurdum.
|>>(sp?)
|>>
|>>Anyway, it's not t>t, it's that T(t) is false if true, but true if
|>>false. Therein lies the contradiction, proving there is no halting
|>>algorithm.
|
|
| I remember a proof where you would make a list of all possible programs
| in an 2d array like:
|
|
| 01100101010
| 00101100101
| 11010111000
| 10011000110
|
| etc.
|
| Then you would prove there was one more 'program' on the turing machine
| by taking the first bit from T(1), the second from T(2), etc. and then
| reverse all those bits proving an additional program exists that you
| didn't count at first.

Wouldn't that prove that there are infinitely many programs, not that
you can't tell whether they halt?

| But that was years ago for me (1996). I don't really remember the
| details of what the proof was about but it seemed to me that you could
| use something that like to proof that Pi is larger than the Pi you
| calculated before.
|
| Thomas
| --
| "All my life, I've always wondered, What it would be like to fire a
| ballistic missile" - Wonderfully colored plastic war toys, The Dead
| Milkmen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0-ecc0.1.6 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQEVAwUBQiX5fuBz3eKRGXGfAQOqegf+JHa+gaURFVcDzkZ/EL42QSwS4mVsY8Dr
DzEpP3VOGAmW6H8uAeaNcSH1NVcmhoWLDXDxNPhj+EGljxG5S8CSyp83ALR59Hin
rCnPVbjp/wMqFclx165N6p+P5SDzOVUo3MUzZv5iiDdYODgJX5Bv4RNBbJOkUJKj
PILGEx1YLdlSE8TJchLJxct6GsZqMvKvY8FAz5Cr3X+ZcXkrs+P0vUiHMr5kGcW4
W2DFB9X5GhABplL8L8pgu7jmc2MW0QzPW4ubeFjZMd9yGgRJe7XV+qhL9W2cdrkQ
sydJ6mvUaKPbAzsCd5lciRWaBbmV/OzuC1mHzWsBC73mH6Cy8KeVfA==
=fnJx
-----END PGP SIGNATURE-----
 >> Stay informed about: Creatures is eating my brain. 

-----BEGIN PGP SIGNED MESSAGE-----

bd wrote:
> Thomas J. Boschloo wrote:
> | bd wrote:
> |
> |>>nornagon wrote:
> |>>| Thomas J. Boschloo InSaNiTised:

> |>>|>bd wrote:
> |>>|>| Vadim wrote:
> |>>|>| | Predictor wrote:
> |>>|>| |
> |>>|>| |
> |>>|>| |>>nornagon wrote:
> |>>|>| |>>
> |>>|>| |>>>But yes, Turing machines can, by definition, do anything.
> |>>|>| |>>
> |>>|>| |>>
> |>>|>| |>>Can a Turing machine make a bowl of soup? Can it walk a dog?
> |>>|>| |
> |>>|>| | Of course it can!
> |>>|>| |
> |>>|>| | It could make a virtual bowl of soup or walk a virtual dog inside
> |>>|>| | the world it simulates.
> |>>|>| |
> |>>|>| | I mean, we all play Creatures games here
> |>>|>| |
> |>>|>| |
> |>>|>| |>>More importantly, can a Turing machine solve the Halting
> |>>|>| |>>Problem?
> |>>|>| |
> |>>|>| | Nothing can solve the halting problem. For example, does a
> |>>|>| | program that search for this post in Pi halt? We don't know.
> |>>|>| | It's perfectly possible that this post doesn't even happen in
> |>>|>| | the infinity of Pi. Or maybe it does.
> |>>|>|
> |>>|>| IIRC, wasn't it proven that it does?
> |>>|>|
> |>>|>| Better to use the original proof (paraphrased):
> |>>|>|
> |>>|>| Let H(p,i) be a function which takes as input the strings p and i
> and
> |>>|>| returns a boolean value indicating whether running the program
> |>>|>| represented by p with input i halts.
> |>>|>|
> |>>|>| Let T(s) be a program which evaluates H(s, s), and halts if H(s, s)
> |>>|>| returns false.
> |>>|>|
> |>>|>| Since all algorithms can be represented by strings, T must have
> such a
> |>>|>| string. Call it t.
> |>>|>|
> |>>|>| What is T(t)?
> |>>|>
> |>>|>Now you have to proof that t>t, but I am tired
> |>>|>
> |>>|
> |>>|
> |>>| t can't be greater than t. O.o
> |>>|
> |>>
> |>>Reductio ad absurdum.
> |>>(sp?)
> |>>
> |>>Anyway, it's not t>t, it's that T(t) is false if true, but true if
> |>>false. Therein lies the contradiction, proving there is no halting
> |>>algorithm.
> |
> |
> | I remember a proof where you would make a list of all possible programs
> | in an 2d array like:
> |
> |
> | 01100101010
> | 00101100101
> | 11010111000
> | 10011000110
> |
> | etc.
> |
> | Then you would prove there was one more 'program' on the turing machine
> | by taking the first bit from T(1), the second from T(2), etc. and then
> | reverse all those bits proving an additional program exists that you
> | didn't count at first.
>
> Wouldn't that prove that there are infinitely many programs, not that
> you can't tell whether they halt?

Probably It's been a while since I learned this (about ten years ago
I think).

<I just stapled my slippers that just tore on the side, and it hurts
when I walk on them because I stapled them the wrong way! WIP (work in
progress)>

Can't find the book though. Formal Theory of Automata I think it was
called. It was red and had a hard cover..

Thomas
- --
"All my life, I've always wondered, What it would be like to fire a
ballistic missile" - Wonderfully colored plastic war toys, The Dead
Milkmen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQB5AwUBQimfBwEP2l8iXKAJAQGmVwMguACjQJqL2ackpcNbN+uRiLTQ2UOF+5UR
Qwf7hbGiDxWNPkD7YHg6wcvxYKFCVgnBCp0qG7BZzizCxrlRntzc/W+bLRavsEP8
+65Lr1proJGuLstus2AI2fs8rACCIa89/SplPA==
=Rh70
-----END PGP SIGNATURE-----
 >> Stay informed about: Creatures is eating my brain.