Pseudolinguagem para caracterizar funções recursivas

Abstract

Iniciamos esse artigo com uma visão geral sobre a Teoria da Computabilidade e o conceito de algoritmo. Em seguida, definimos a classe de funções recursivas, uma tentativa de formalização da classe de funções algor´ıtmicas, e mostramos como muitas funções usualmente dispon´ıveis nas linguagens de programação são casos de funções recursivas. A partir daí caminhamos para a construção de uma pseudolinguagem de programação que dê conta exatamente das funções recursivas, buscando criar uma ponte entre os conceitos da Teoria da Computabilidade e a programação prática. Desenvolvemos duas versões para essa pseudolinguagem, a ˜REC, com um escopo menor de operações, e a ˜REC++, que oferece alguns recursos que facilitam a codificac¸ao. Durante a apresentação dessas linguagens, procuramos demonstrar a equivalência entre a classe das funções ˜REC e REC++ calculáveis com a classe das funções recursivas.