All of lore.kernel.org
 help / color / mirror / Atom feed
From: "H. Peter Anvin" <hpa@zytor.com>
To: Ben Clifford <benc@hawaga.org.uk>
Cc: Johannes Schindelin <Johannes.Schindelin@gmx.de>,
	Git Mailing List <git@vger.kernel.org>
Subject: Re: Problem merging
Date: Sun, 27 Nov 2005 13:24:44 -0800	[thread overview]
Message-ID: <438A241C.5010007@zytor.com> (raw)
In-Reply-To: <D8B7EF65-9D0C-4706-B248-4B7C118C16BF@hawaga.org.uk>

Ben Clifford wrote:
> On 24 Nov 2005, at 00:49, Johannes Schindelin wrote:
> 
>>
>> I think nobody is. Since there are infinitely many files having the  same
>> SHA1 (pigeon-hole principle),
> 
> hmm... pigeon-hole principle is just that there exists two files that  
> have the same SHA-1 as each other... doesn't say anything about *all*  
> SHA-1s, though?
> 

There are an infinite number of possible files (specifically, 
aleph-null.)  There are a finite number of possible SHA-1's 
(specifically, 1461501637330902918203684832716283019655932542976.) 
Therefore the pidgeon-hole principle tells you there must be at least 
one SHA-1 value that hashes an infinite number of files (aleph-null, again.)

Given that SHA-1 is believed to be uniformly distributed, it's quite 
likely *ALL* SHA-1's hash an infinite number of files, but the 
pigeon-hole principle can't tell you that.

	-hpa

  parent reply	other threads:[~2005-11-27 21:25 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2005-11-23  2:50 Problem merging Luben Tuikov
2005-11-23  3:06 ` Junio C Hamano
2005-11-23  3:41   ` Luben Tuikov
2005-11-23 14:49   ` Johannes Schindelin
2005-11-24 10:54     ` Ben Clifford
2005-11-25  1:13       ` Johannes Schindelin
2005-11-25  1:35       ` Andreas Ericsson
2005-11-27 21:24       ` H. Peter Anvin [this message]
2005-11-23  8:59 ` Fredrik Kuivinen
2005-11-23 19:48   ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=438A241C.5010007@zytor.com \
    --to=hpa@zytor.com \
    --cc=Johannes.Schindelin@gmx.de \
    --cc=benc@hawaga.org.uk \
    --cc=git@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.