# Logic in computer science

##### May 27, 2014 by Florian Aigner

All men are mortal. Socrates is a man. Therefore, Socrates is mortal. Logical arguments like this one have been studied since antiquity. In the last few decades, however, logic research has changed considerably: the computer sciences were born. The success of informatics would have been impossible without the groundwork provided by logicians β and, in turn, computer sciences keep posing new interesting questions, which can only be answered by formal logic. Informatics is not the modern-day successor of logic, both fields keep moving forward, hand in hand.

Calculating Logical Statements

Simple logical conclusions such as the famous syllogism about Socrates' mortality appear clear and simple to us. But is not just about formalizing the obvious. Just like in mathematics, logic allows us to construct arbitrarily complex equations, to do sophisticated calculations, to analyse the world.

Even before the first electronic calculating devices were built, research on the hypothetical possibilities of computers was done: in the 1930s, the mathematicians Alan Turing and Alonzo Church characterized the class of mathematical problems which can in principle be tackled. Turing put forward an intriguingly simple model for a calculating machine β the Turing machine: It moves on an infinitely long ribbon, reads numbers and changes it according to a given set of rules.

Such a machine can be built with mechanical gears or lego bricks. Although in practice such a machine is highly inefficient, one can show that in principle any conceivable computer calculation can be carried out by such a simple device. With the Turing machine it became possible to clearly define what "doing mathematical calculations" even means. Using this concept, Turing could show that some questions can never be answered by a computer: a computer program which reads other programs and then decides whether its calculations would ever come to a halt or go on forever is logically impossible.

Looking inward, looking outward

"Today, most of the research in logic is done by computer scientists, not by mathematicians", says Professor Helmut Veith from the Vienna University of Technology. Logic in has to fulfil several tasks. First of all, it is a tool with which can describe the world. Logic is used for databases or for creating artificial intelligence.

But logic does not only help a computer to view the world, it also offers the possibility of introspection: computer codes can check other computer codes and look for logical errors. "It is similar to the way we humans think", says Helmut Veith. "We think about the world around us, but we can also contemplate ourselves and our own mind."

Logic-based quality checks of computer codes (verification, model checking) play an important role for industry and the economy. When a user tests a program and finds that it works, this does not by all means guarantee that the program is free of errors. The crucial question is: does the code react correctly to any conceivable input, in any logically possible situation? This can only be determined by an automated program.

Such a reliable check is particularly important for security relevant code such as airplane controls. Logical checks are essential for the production of computer chips as well. Today, chips start out as a program, long before they are physically built. No human being could ever determine by hand whether the chip does indeed react correctly to any given situation. Computer programs carry out this task. With their logical checks, they ensure our safety.

## Related Stories

#### Study reveals details of logical circuits built using living slime molds

March 27, 2014

A future computer might be a lot slimier than the solid silicon devices we have today. In a study published in the journal Materials Today, European researchers reveal details of logic units built using living slime molds, ...

#### Artificial muscle computer performs as a universal Turing machine

March 28, 2013

(Phys.org) βIn 1936, Alan Turing showed that all computers are simply manifestations of an underlying logical architecture, no matter what materials they're made of. Although most of the computer's we're familiar with are ...

#### Kasparov versus Turing (w/ Video)

June 27, 2012

(Phys.org) -- For the first time in public, Mr. Kasparov played a match against Turing’s chess program live on stage at The University of Manchester’s Alan Turing Centenary Conference.

#### Computer scientists form mathematical formulation of the brain's neural networks

April 2, 2012

As computer scientists this year celebrate the 100th anniversary of the birth of the mathematical genius Alan Turing, who set out the basis for digital computing in the 1930s to anticipate the electronic age, they still quest ...

#### Mathematician sees artistic side to father of computer

February 23, 2012

This year a series of events around the world will celebrate the work of Alan Turing, the father of the modern computer, as the 100th anniversary of his birthday approaches on June 23. In a book chapter that will be published ...

#### Difficulty makes Candy Crush so addictive

March 13, 2014

It's been said that in a city, you're never more than two metres away from a rat. But it seems more likely that you're never more than two metres from someone playing the puzzle game Candy Crush Saga.

## Recommended for you

#### Samsung to disable Note 7 phones in recall effort

December 9, 2016

Samsung announced Friday it would disable its Galaxy Note 7 smartphones in the US market to force remaining owners to stop using the devices, which were recalled for safety reasons.

#### Michigan lets autonomous cars on roads without human driver

December 9, 2016

Companies can now test self-driving cars on Michigan public roads without a driver or steering wheel under new laws that could push the state to the forefront of autonomous vehicle development.

#### This is 'year zero' of a virtual reality revolution say filmmakers

December 8, 2016

The first wave of virtual reality cinemas, heralding what their creators claim will be an entertainment revolution, rolls out across the world this month.

#### Car company offering red light-reading vehicles in Las Vegas

December 7, 2016

On the theory that a driver who knows when a red light will turn green is more relaxed and aware, vehicle manufacturer Audi is unveiling this week in Las Vegas a technology that enables vehicles to "read" traffic signals ...

#### Swiss unveil stratospheric solar plane

December 7, 2016

Just months after two Swiss pilots completed a historic round-the-world trip in a Sun-powered plane, another Swiss adventurer on Wednesday unveiled a solar plane aimed at reaching the stratosphere.

#### Solar panels repay their energy 'debt': study

December 6, 2016

The climate-friendly electricity generated by solar panels in the past 40 years has all but cancelled out the polluting energy used to produce them, a study said Tuesday.

## 0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.