Do you have adblock enabled?
If you can read this, either the style sheet didn't load or you have an older browser that doesn't support style sheets. Try clearing your browser cache and refreshing the page.

(Gizmodo)   Three problems computers will never be able to solve. Well, four if you count the algorithm for love   (gizmodo.com ) divider line 42
    More: Interesting, New Scientist, halting problem  
•       •       •

4990 clicks; posted to Geek » on 17 Jul 2014 at 4:59 PM (1 year ago)   |   Favorite    |   share:  Share on Twitter share via Email Share on Facebook   more»



42 Comments   (+0 »)
   
View Voting Results: Smartest and Funniest

Archived thread
 
2014-07-17 04:05:11 PM  
imgs.xkcd.com
 
2014-07-17 05:03:42 PM  
42
 
2014-07-17 05:04:32 PM  
I'm scared to do a Google search for Wang Tiles.
 
2014-07-17 05:06:42 PM  

Mad_Radhu: I'm scared to do a Google search for Wang Tiles.


Searching for Wang and Penrose tiles will likely get you there with minimal penises.  Or you could click the link in TFA which goes to the wiki page.
 
2014-07-17 05:12:09 PM  

Teiritzamna: Searching for Wang and Penrose tiles will likely get you there with minimal penises.  Or you could click the link in TFA which goes to the wiki page.


How can I get there with maximal penises?
 
2014-07-17 05:14:17 PM  
www.specialeducationadvisor.com
 
2014-07-17 05:29:41 PM  
in out repeat
 
2014-07-17 05:37:44 PM  
The exact value of pi ?
 
2014-07-17 05:41:25 PM  
dilbert.com
 
2014-07-17 05:55:56 PM  

Uzzah: Teiritzamna: Searching for Wang and Penrose tiles will likely get you there with minimal penises.  Or you could click the link in TFA which goes to the wiki page.

How can I get there with maximal penises?


You just need to solve for optimal tip-to-tip efficiency 

i1.ytimg.com
 
2014-07-17 05:59:26 PM  
Well given that the halting problem is by definition something that can't be solved by any means, yeah a computer isn't going to be able to solve it.
 
2014-07-17 06:30:21 PM  
Isn't it wonderful? Master Hugh has finally found a true love.

31.media.tumblr.com
 
2014-07-17 06:31:59 PM  

WhyteRaven74: Well given that the halting problem is by definition something that can't be solved by any means, yeah a computer isn't going to be able to solve it.


HUH?
The halting problem is solvable within many restricted classes of computer programs, just not in general.

The halting problem is related to the word problem in math. For groups
The following groups have a solvable word problem:
    Automatic groups, including:
        Finite groups
        Polycyclic groups
        Negatively curved groups
        Euclidean groups
        Coxeter groups
        Braid groups
        Geometrically finite groups
    Finitely generated recursively absolutely presented groups,[8] including:
        Finitely presented simple groups.
    Finitely presented residually finite groups
    One relator groups[9] (this is a theorem of Magnus), including:
        Fundamental groups of closed orientable two-dimensional manifolds.
    Combable groups
 
2014-07-17 06:37:27 PM  
We humans can't solve them either, so why restrict it to computers?
 
2014-07-17 06:39:57 PM  

IgG4: Uzzah: Teiritzamna: Searching for Wang and Penrose tiles will likely get you there with minimal penises.  Or you could click the link in TFA which goes to the wiki page.

How can I get there with maximal penises?

You just need to solve for optimal tip-to-tip efficiency 

[i1.ytimg.com image 480x360]


My favorite part of that joke, is that they actually researched it and everything in the episode was accurate. It made me "extra" appreciate the show.

http://www.scribd.com/doc/228831637/Optimal-Tip-to-Tip-Efficiency
 
2014-07-17 06:43:44 PM  
Just count up the feelings and divide them up even.
 
2014-07-17 07:04:55 PM  

Preebs: My favorite part of that joke, is that they actually researched it and everything in the episode was accurate. It made me "extra" appreciate the show.

http://www.scribd.com/doc/228831637/Optimal-Tip-to-Tip-Efficiency


It's also made walking up to someone and saying "Do you know how long it would take you to jerk off everyone in this room? I do and I can prove it," socially acceptable.
 
2014-07-17 07:13:50 PM  

WhyteRaven74: Well given that the halting problem is by definition something that can't be solved by any means, yeah a computer isn't going to be able to solve it.


I'm not enough of a geek, but I don't get what the halting problem is.  Say you write something like:

do while 1 = 1
 print "go fark yerself!"
loop

Is that obvious that it would run forever?
 
2014-07-17 07:26:29 PM  

downstairs: I'm not enough of a geek, but I don't get what the halting problem is.


You can prove that some programs will halt, or will run forever. The trick is to find a general method which will work for any program.

n = random_positive_integer()
while (n != 1)

{
  if (n mod 2 == 0)
    n = n / 2
  else
    n = 3*n + 1

}
 
2014-07-17 07:26:34 PM  

Preebs: IgG4: Uzzah: Teiritzamna: Searching for Wang and Penrose tiles will likely get you there with minimal penises.  Or you could click the link in TFA which goes to the wiki page.

How can I get there with maximal penises?

You just need to solve for optimal tip-to-tip efficiency 

[i1.ytimg.com image 480x360]

My favorite part of that joke, is that they actually researched it and everything in the episode was accurate. It made me "extra" appreciate the show.

http://www.scribd.com/doc/228831637/Optimal-Tip-to-Tip-Efficiency


Ha! that is awesome. Talk about doing your homework!
 
2014-07-17 07:28:10 PM  
How many licks does it take to get to the center of a midget transformer?
 
2014-07-17 07:48:56 PM  

Science_Guy_3.14159: he exact value of pi ?


It's not hard to represent in base pi numbers.  It's 1.
 
2014-07-17 08:06:09 PM  

WhyteRaven74: Well given that the halting problem is by definition something that can't be solved by any means, yeah a computer isn't going to be able to solve it.


poundgrayly: We humans can't solve them either, so why restrict it to computers?


Right. And in popsci journalism all we're really interested in is the human/computer competitions, so we all know that's implied in the discussion.

So take the Kolmogorov complexity for example. If you'll allow a half-assed Kolmogorov complexity, humans and any animal with eyes can do this better than a computer for large ("large") data sets that can be usefully ("usefully") represented visually. Because Kolmogorov complexity has a lot to do with the visual alikeness of two (or more) different subsets of a set. In other words the Kolmogorov complexity of a bunch of like things (money, for example) thrown onto the ground in front of you comes pretty naturally to the animal brain: Look at it and see what looks the same. Note how everything has turned every which way. Then figure the differences in years, serial numbers, scratches, whatever other markings. You're done.

Meanwhile, half-assed halting problem is useless and no one cares what your best guess is because I can't do anything with that.
 
2014-07-17 08:18:25 PM  

ThrobblefootSpectre: Science_Guy_3.14159: he exact value of pi ?

It's not hard to represent in base pi numbers.  It's 1.


10
 
2014-07-17 08:24:25 PM  

JinxedLynx: ThrobblefootSpectre: Science_Guy_3.14159: he exact value of pi ?

It's not hard to represent in base pi numbers.  It's 1.

10


Oops, yeah, farked that up.  It was tongue in cheek, but the point is there.  Just because rational bases aren't good at representing irrationals doesn't mean we can't represent pi exactly.  It can also be expressed as a ratio, a convergent series, a summation, or a continued fraction.
 
2014-07-17 09:21:39 PM  
Love is mutual comprehension, humans are adapted to be learning-concentric, therefore it only exists as a statistical anomaly.
 
2014-07-17 09:27:56 PM  
can computers make a burrito so big they cannot compute all of it
 
2014-07-17 09:30:02 PM  
Well, actually more of a continuum across the most broad spectrum statistical manifests, all in the same it is usually canceled out by the effect of observance, leaving operations in a state of emotional incongruity if magnified through attention or focal parameters.
 
2014-07-17 11:16:48 PM  

downstairs: WhyteRaven74: Well given that the halting problem is by definition something that can't be solved by any means, yeah a computer isn't going to be able to solve it.

I'm not enough of a geek, but I don't get what the halting problem is.  Say you write something like:

do while 1 = 1
 print "go fark yerself!"
loop

Is that obvious that it would run forever?


The problem lies with more complex examples than that.

Here is the proof:
Assume we have a function (let's call it f) which will take an input of another function (and input) and returns true if it halts, false if it does not halt (that is, it solves the halting problem). So, f(g, i), where g is the function, i is the input

Now, let's have another function, let's call it h.
h(i): 
If f(h,i) = true then
   while (1) {}   // infinite loop
else return

So now, we just invalidated the function. If f says h will infinite loop, it actually does not, while if h says it will not infinite loop, it actually does. You can also use this to prove Rice's theorem (that is, a function cannot determine the non-trivial behavior of another function).
 
2014-07-18 05:44:14 AM  

Ivo Shandor: The trick is to find a general method which will work for any program.


...and is more efficient than simply executing the program. The brute-force method works for any program, it just takes an unbound amount of time.
 
2014-07-18 06:35:31 AM  
Machines can feel love.

gifmansion.com
 
2014-07-18 08:05:23 AM  

Ivo Shandor: The trick is to find a general method which will work for any program.


If it's running on Windows ME, it will halt...
 
2014-07-18 09:32:15 AM  

Xxplosiv: Love is mutual comprehension, humans are adapted to be learning-concentric, therefore it only exists as a statistical anomaly.


Well it only has to happen one in your life time, if you are doing it right. (Or wrong...)
 
2014-07-18 09:57:13 AM  

ThrobblefootSpectre: JinxedLynx: ThrobblefootSpectre: Science_Guy_3.14159: he exact value of pi ?

It's not hard to represent in base pi numbers.  It's 1.

10

Oops, yeah, farked that up.  It was tongue in cheek, but the point is there.  Just because rational bases aren't good at representing irrationals doesn't mean we can't represent pi exactly. It can also be expressed as a ratio, a convergent series, a summation, or a continued fraction.


Cool. Show us the ratio (of integers, of course).
 
2014-07-18 11:13:44 AM  
What is the ninth busy beaver number?
 
2014-07-18 11:23:19 AM  

Also, I always liked the quote, attributed to Paul Erdos, about Ramsey numbers:

Imagine an alien race, vastly more powerful than us, comes to Earth and says they will destroy us unless we can find the value of R(5,5). We should immediately gather up all the mathematicians and computing resources on Earth to attempt to determine the answer. But if the aliens were instead to ask us for R(6,6), we should immediately gather up all the soldiers and military resources on Earth to attempt to destroy the aliens.


Of course, that's not really the same sort of thing as the article - it is, in principle, possible to calculate R(6,6), it would just take a really long time. The article is talking about things that are in principle non-computable.

(The other thing I always loved about Ramsey theory is Graham's number, which is so unimaginably huge that all the atoms in several Universes wouldn't be enough material to write it down. The best part is that Graham's number is the upper bound - and the lower bound is 6.)
 
2014-07-18 11:38:36 AM  

Lord Dimwit: The other thing I always loved about Ramsey theory is Graham's number, which is so unimaginably huge that all the atoms in several Universes wouldn't be enough material to write it down.


imgs.xkcd.com
 
2014-07-18 12:48:03 PM  
The exact value of Pi is 3, according to Common Core.
The math is much easier that way.
 
2014-07-18 12:48:47 PM  
www.asofterworld.com
 
2014-07-18 01:06:21 PM  

Ivo Shandor: Lord Dimwit: The other thing I always loved about Ramsey theory is Graham's number, which is so unimaginably huge that all the atoms in several Universes wouldn't be enough material to write it down.

[imgs.xkcd.com image 350x891]


I've found that mostly XKCD means "this is never funny"
 
2014-07-18 01:42:18 PM  

SuperChuck: Ivo Shandor: Lord Dimwit: The other thing I always loved about Ramsey theory is Graham's number, which is so unimaginably huge that all the atoms in several Universes wouldn't be enough material to write it down.

[imgs.xkcd.com image 350x891]

I've found that mostly XKCD means "this is never funny"


Calling the Ackermann function with Graham's number is funny, though. I could just imagine there being an integer overflow in the Universe and we crash or something.
 
2014-07-18 02:23:29 PM  

DogBoyTheCat: The exact value of Pi is 3, according to Common Core the Bible.
The math is much easier that way.


FTFY
 
Displayed 42 of 42 comments

View Voting Results: Smartest and Funniest


This thread is archived, and closed to new comments.

Continue Farking
Submit a Link »
Advertisement
On Twitter






In Other Media


  1. Links are submitted by members of the Fark community.

  2. When community members submit a link, they also write a custom headline for the story.

  3. Other Farkers comment on the links. This is the number of comments. Click here to read them.

  4. Click here to submit a link.

Report