Paulo Veloso foi professor do Departamento de Informática de 1977 até 1995. Veloso foi um dos pilares do Departamento e teve atuação de destaque internacional nas áreas de Lógica e Teoria da Computação.
Ele contribuiu para a formação de numerosos mestres e doutores, entre os quais o atual diretor, prof. Markus Endler, cuja dissertação de mestrado orientou. Passou a atuar como professor titular na UFRJ e foi membro ativo do corpo docente do PESC, Programa de Engenharia de Sistemas e Computação, da COPPE/UFRJ, onde se aposentou, mas nunca deixou de frequentar e colaborar com a PUC-Rio.
Veloso desenvolveu em 1984 a Teoria Geral dos Problemas, usada até hoje com a Teoria de Problemas de Kolmogorov, russo que é um dos fundamentadores da Teoria da Probabilidade. Outra contribuição importante foi o Teorema da Modularização, na década de 1990, fundamentando a teoria de desenvolvimento de software e sistemas.
Por sua valorosa contribuição, Veloso recebeu homenagens e premiações, como o Prêmio Almirante Álvaro Alberto para Ciência e Tecnologia: Área de Informática, do CNPq, em 1993; Prêmio Cientista do Nosso Estado pela FAPERJ, em 2002; foi eleito membro do CLE: Centro de Lógica, Epistemologia e História da Ciência da UNICAMP, em 2003 e, em 2014 foi homenageado em seu aniversário de 70 anos, no Encontro Brasileiro de Lógica.
Edward Hermann docente do quadro principal do DI da PUC-Rio, que trabalhou lado a lado com Veloso nos últimos anos, por exemplo na pesquisa sobre Fundamentação de Inteligência Artificial, lembra que Veloso era conhecido por fazer apenas uma pergunta em defesas e apresentações de seminários e trabalhos em congressos. A pergunta geralmente causava grande impacto. O professor Hermann também informou a todos sobre a preparação em andamento de um Festschrift - livro-homenagem - para ele, pela College Publications, do Imperial College London, intitulado A Question is more Illuminating than an Answer.
