EDB — 1YK

view in whole PDF view in whole HTML

Vista

Italiano

[1YK] Si può determinare se una formula è ben formata facendo un numero finito di controlli usando le regole precedenti: infatti le regole stabiliscono che ogni formula ben formata si deve poter spiegare in termini di formule ben formate che sono più corte di lei. Dunque la affermazione “questa formula è ben formata” è “decidibile”.  1

  1. La definizione precisa di “decidibile” esula da queste note. Pensate a un algoritmo scritto al computer che, data una formula, con un numero finito di passaggi risponda “ben formata” oppure “non ben formata”. Notate però che il numero di controlli da fare cresce esponenzialmente con la lunghezza della formula.
Scarica PDF
Bibliografia
Indice analitico
  • formula, ben formata
Stai gestendo il blob in: Multiple languages
Questo contenuto è disponibile in: Italiano Inglese