EDB — 1YK

view in whole PDF view in whole HTML

View

Italian

[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.
Download PDF
Bibliography
Book index
  • formula, ben formata
Managing blob in: Multiple languages
This content is available in: Italian English