Maybe its pervasiveness has long obscured its origins. But Unix, the operating system that in one derivative or another powers nearly all smartphones sold worldwide, was born 50 years ago from the failure of an ambitious project that involved titans like Bell Labs, GE, and MIT. Largely the brainchild of a few programmers at Bell Labs, the unlikely story of Unix begins with a meeting on the top floor of an otherwise unremarkable annex at the sprawling Bell Labs complex in Murray Hill, New Jersey.#History #ComputerHistory #Unix #OperatingSystems #ComputerScience #Computers
It wasn’t until late 1971 that the computer science department got a truly modern computer. The Unix team had developed several tools designed to automatically format text files for printing over the past year or so. They had done so to simplify the production of documentation for their pet project, but their tools had escaped and were being used by several researchers elsewhere on the top floor. At the same time, the legal department was prepared to spend a fortune on a mainframe program called “AstroText.” Catching wind of this, the Unix crew realized that they could, with only a little effort, upgrade the tools they had written for their own use into something that the legal department could use to prepare patent applications.
The computer science department pitched lab management on the purchase of a DEC PDP-11 for document production purposes, and Max Mathews offered to pay for the machine out of the acoustics department budget. Finally, management gave in and purchased a computer for the Unix team to play with. Eventually, word leaked out about this operating system, and businesses and institutions with PDP-11s began contacting Bell Labs about their new operating system. The Labs made it available for free—requesting only the cost of postage and media from anyone who wanted a copy.
A paper posted online this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This “sensitivity” conjecture has stumped many of the most prominent computer scientists over the years, yet the new proof is so simple that one researcher summed it up in a single tweet.#Mathematics #Proofs #Conjectures #ComputerScience
“This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson of the University of Texas, Austin, in a blog post. “The list of people who tried to solve it and failed is like a who’s who of discrete math and theoretical computer science,” he added in an email.
Imagine, Mathieu said, that you are filling out a series of yes/no questions on a bank loan application. When you’re done, the banker will score your results and tell you whether you qualify for a loan. This process is a Boolean function: Your answers are the input bits, and the banker’s decision is the output bit.
If your application gets denied, you might wonder whether you could have changed the outcome by lying on a single question — perhaps, by claiming that you earn more than $50,000 when you really don’t. If that lie would have flipped the outcome, computer scientists say that the Boolean function is “sensitive” to the value of that particular bit. If, say, there are seven different lies you could have told that would have each separately flipped the outcome, then for your loan profile, the sensitivity of the Boolean function is seven.
Computer scientists define the overall sensitivity of the Boolean function as the biggest sensitivity value when looking at all the different possible loan profiles. In some sense, this measure calculates how many of the questions are truly important in the most borderline cases — the applications that could most easily have swung the other way if they’d been ever so slightly different.
Sensitivity is usually one of the easiest complexity measures to compute, but it’s far from the only illuminating measure. For instance, instead of handing you a paper application, the banker could have interviewed you, starting with a single question and then using your answer to determine what question to ask next. The largest number of questions the banker would ever need to ask before reaching a decision is the Boolean function’s query complexity.
This measure arises in a host of settings — for instance, a doctor might want to send a patient for as few tests as possible before reaching a diagnosis, or a machine learning expert might want an algorithm to examine as few features of an object as possible before classifying it. “In a lot of situations — diagnostic situations or learning situations — you’re really happy if the underlying rule … has low query complexity,” O’Donnell said.
Fernando Corbató, whose work on computer time-sharing in the 1960s helped pave the way for the personal computer, as well as the computer password, died on Friday at a nursing home in Newburyport, Mass. He was 93.#ComputerHistory #Obituaries #Computers #ComputerScience #OperatingSystems
His wife, Emily Corbató, said the cause was complications of diabetes. At his death he was a professor emeritus at the Massachusetts Institute of Technology.
Dr. Corbató, who spent his entire career at M.I.T., oversaw a project in the early 1960s called the Compatible Time-Sharing System, or C.T.S.S., which allowed multiple users in different locations to access a single computer simultaneously through telephone lines.
In the course of refining time-sharing systems in the 1960s, Dr. Corbató came up with another novelty: the computer password.
C.T.S.S. gave each user a private set of files, but the lack of a login system requiring a password meant that users were free to peruse others’ files.
“Putting a password on for each individual user as a lock seemed like a very straightforward solution,” Dr. Corbató told Wired magazine in 2012. The passwords for C.T.S.S. are widely considered to be among the earliest computer security mechanisms.