git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: Problem merging

From
HAH. Peter Anvin <hpa@zytor.com>
Date
Nov 27, 2005, 21:24 UTC
Message-ID
<438A241C.5010007@zytor.com>
In-Reply-To
<D8B7EF65-9D0C-4706-B248-4B7C118C16BF@hawaga.org.uk>
Ben Clifford wrote:
Show 10 quoted lines
> 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
Previous: Andreas EricssonNext: Fredrik Kuivinen
Message 8 of 10 in “Problem merging”
  1. Luben TuikovNov 23, 2005
  2. Junio C HamanoNov 23, 2005
  3. Luben TuikovNov 23, 2005
  4. Johannes SchindelinNov 23, 2005
  5. Ben CliffordNov 24, 2005
  6. Johannes SchindelinNov 25, 2005
  7. Andreas EricssonNov 25, 2005
  8. H. Peter AnvinNov 27, 2005
  9. Fredrik KuivinenNov 23, 2005
  10. Junio C HamanoNov 23, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.