# data[].attributes.body
A lógica computacional é o uso da lógica para realizar ou raciocinar sobre a computação. Ela tem uma relação semelhante com a ciência da computação e a engenharia, assim como a lógica matemática com a matemática e a lógica filosófica com a filosofia. É sinônimo de "lógica na ciência da computação".

O termo “lógica computacional” ganhou destaque com a fundação da ACM Transactions on Computational Logic em 2000. No entanto, o termo foi introduzido muito antes, por J.A. Robinson em 1970. A expressão é usada no segundo parágrafo com uma nota de rodapé alegando que "lógica computacional" é "certamente uma frase melhor do que 'prova de teorema', para o ramo da inteligência artificial que trata de como fazer com que as máquinas façam deduções com eficiência".

A lógica computacional também passou a ser associada à programação lógica, porque muitos dos primeiros trabalhos em programação lógica no início dos anos 1970 também ocorreram no Departamento de Lógica Computacional em Edimburgo. Foi reutilizado no início dos anos 1990 para descrever o trabalho em extensões de programação lógica no Projeto de Pesquisa Básica da UE "Compulog" e na Rede de Excelência associada. Krzysztof Apt, que era o coordenador do Projeto de Pesquisa Básica Compulog-II, reutilizou e generalizou o termo quando fundou a ACM Transactions on Computational Logic em 2000 e se tornou seu primeiro Editor-Chefe.

# data[].attributes.attachment_link.readable_text
Promote Your Work with Kudos

is a free service that you can use to promote your work more effectively. After your paper has been accepted and uploaded to the ACM Digital Library, you'll receive an invitation from Kudos to create an account and add a plain-language description. Click here for further information.

Publons Reviewer Recognition Program

In an effort to better serve-and incentivize-ACM reviewers, ACM has partnered with the Publons Reviewer Recognition Service, which allows reviewers to create a profile and to track, verify and promote their efforts for ACM publications. Click here for further information.

# data[].attributes.attachment_link.description
Promote Your Work with Kudos is a free service that you can use to promote your work more effectively. After your paper has been accepted and uploaded to the ACM Digital Library, you'll receive an invitation from Kudos to create an account and add a plain-language description. Click here for further information.

# data[].attributes.body
John McCarthy(1958) foi o primeiro a publicar uma proposta de uso da lógica matemática para programação. A primeira linguagem de programação lógica foi a Planner, a qual permitia a invocação orientada a padrões de planos procedimentais de asserções e de objetivos.

# data[].attributes.body
Turing Machines é um exemplo do uso da lógica computacional.

Uma Turing Machine é um modelo matemático de computação que define uma máquina abstrata que manipula símbolos em uma tira de fita adesiva de acordo com uma tabela de regras. Apesar da simplicidade do modelo, dado qualquer algoritmo computacional, uma Turing Machine capaz de simular a lógica desse algoritmo pode ser construída.

# data[].attributes.attachment_link.readable_text
1. write a symbol to the current tape cell

2. move to the left or right by one cell

3. set the new state

That's it!

A Turing machine is an abstract device to model computation as rote symbol manipulation.

Each machine has a finite number of states, and a finite number of possible symbols. These are fixed before the machine starts, and do not change as the machine runs.

There are an infinite number of tape cells, however, extending endlessly to the left and right. Each tape cell bears a symbol. Any cell not part of the input or not yet written to bears the blank symbol by default. Notice that at any step, only finitely many cells bear a non-blank symbol.

(As a mathematical model, a Turing machine has infinite memory (an infinite tape) so as to not artificially restrict its power. In practice, many machines of interest take finite memory, and can be fully simulated for manageable input sizes. Even machines that use infinite memory-and hence never halt-use at most one new tape cell per step, and so can be simulated to an extent.)

The formal definition of a Turing machine has slight variations but essentially is a tuple (ordered list) comprising

states Q

start state q₀ &in; Q

input alphabet Σ

tape alphabet Γ, where Σ &subseteq; Γ

blank symbol b &in; Γ

transition function δ that has the type Q × Γ &rightarrow; Γ × {L, R} × Q

where Q, Σ, and Γ are finite nonempty sets. Some definitions also require that the blank symbol not be part of the input (b ∉ Σ).

As an example, a formal description for the "binary increment" machine is as follows:

δ(right, 1) = (1, R, right)
δ(right, 0) = (0, R, right)
δ(right, ' ') = (' ', L, carry)
δ(carry, 1) = (0, L, carry)
δ(carry, 0) = (1, L, done)
δ(carry, ' ') = (1, L, done)

Note that for simplicity, the simulator limits each symbol to one character. Furthermore, input is not checked for conformance with an input alphabet, in exchange for not having to define input and tape alphabets.

(The behavior of a Turing machine can also be described in mathematical terms if desired. Without going into too much detail, this involves defining how a configuration of a machine-its state, tape contents, and tape head position (current cell)-leads to the next configuration, based on the transition function. To start with, the tape's contents may be defined as a function from integers to symbols, with the head position as an integer, and each move {L, R} adding -1 or +1 respectively to the head position.)

Some aspects of the definition vary from author to author, but the differences come down to preference and do not affect computational power. That is, machines on one model can be simulated or converted to run on another model.

Some of the variations you may come across:

1. The tape only extends infinitely to the right. The left end is where the tape head (current cell) begins. Moving left at the left end keeps the tape head on the same cell.

2. In addition to "move left" (L) or "move right" (R), a tape head movement can be "no move" (N).

3. Instead of moving the tape head, a movement shifts the tape itself, so that the directions of L & R are swapped. (Shifting the tape left is the same as moving the head right.)

4. The machine can only halt in one of two states: a state designated the accept state, or another state designated the reject state. These states have no exiting transitions. All the other states must have transitions defined for every symbol.

The simulator was designed with these and other considerations in mind.

1. Limiting the tape was inconvenient, often requiring marking the left end with a symbol, and writing numbers in reverse. On the other hand, machines created for a right-infinite tape can run on a doubly-infinite tape with little to no modification.

2. Compared to L and R, "no move" (N) seems to be seldom used. For now it has been omitted for conceptual simplicity.

3. It's more intuitive to set the current cell directly by moving the tape head. Turing also follows this convention. (The visualization however stays centered on the head to avoid issues of the head moving out of view.)

4. The accept/reject convention still works; it's just not required. In fact the simulator supports a convenient shorthand, demonstrated in some of the examples: omit the reject state and all transitions to it, and treat halting on a non-accept state as an implicit rejecting transition. This reduces tedious boilerplate code and makes for a cleaner diagram.

# Adds 1 to a binary number.
input: '1011'
blank: ' '
start state: right
table:
  # scan to the rightmost digit
  right:
    1: R
    0: R
    ' ': {L: carry}
  # then carry the 1
  carry:
    1: {write: 0, L}
    0: {write: 1, L: done}
    ' ': {write: 1, L: done}
  done:

The general form of an instruction has three parts:
{write: 1, L: done} writes the symbol 1, moves the tape head left (L), and goes to the done state.

{L: carry} writes the same symbol that was read, moves the tape head left, and goes to thecarry state.

R (shorthand for {R}) simply moves the tape head right. It writes back the same symbol and stays in the same state.

# data[].attributes.attachment_link.description
write a symbol to the current tape cell move to the left or right by one cell set the new state That's it! A Turing machine is an abstract device to model computation as rote symbol manipulation. Each machine has a finite number of states, and a finite number of possible symbols.