Logic and Computation, Department of Mathematics, IST University of Lisbon

- Current research interests: Learning theory (recursion theoretical); Scientific philosophy.
- I have the BSc and MSc in Physics, the MSc in Applied Mathematics, the PhD in Mathematics, and the Aggregation (Habilitation) in Computer Science.

__How far from P is NP__, by José Félix Costa, 23 pp., to appear.__Three forms of physical measurement and their computability__, by Edwin Beggs, José Félix Costa and John V. Tucker.*The Review of Symbolic Logic*, to appear.__Uncertainty in time__, by José Félix Costa, Parallel Processing Letters, 2014, to appear.__The Physics of the Halting Problem__(book chapter), by José Félix Costa, in print.__An Analogue-digital Church-Turing Thesis__, by Edwin Beggs, José Félix Costa, Diogo Poças, and John V. Tucker.*International Journal of Foundations of Computer Science*, 25(4): 373 -- 389, 2014.- A natural computation model of positive relativisation, by Edwin Beggs, José Félix Costa, and John V. Tucker,
*International Journal of Unconventional Computing*, 10(1-2): 111--141, Old City Publishing, Inc., 2014. - Incomputability at the Foundations of Physics (A Study in the Philosophy of Science), by José Félix Costa.
*Oxford Journal of Logic and Computation*, 23(6): 1225--1248, 2013.

- Oracles that measure thresholds: The Turing machine and the broken balance, by Edwin Beggs, José Félix Costa, Diogo Poças, and John V. Tucker.
*Oxford Journal of Logic and Computation*, 23(6): 1155--1181, 2013. - The ARNN model relativizes P == NP and P =/= NP, by José Félix Costa and Raimundo Leong,
*Theoretical Computer Science*, 499(1): 2--22, Elsevier, August 12, 2013. - On the power of threshold measurements as oracles, by Edwin Beggs, José Félix Costa, Diogo Poças, and John V. Tucker. Giancarlo Mauri, Alberto Dennunzio, Luca Manzoni, and Antonio E. Porreca (Editors), Unconventional Computation and Natural Computation,
*Lecture Notes in Computer Science*7956:6--18, Springer-Verlag, 2013. - Processes with Infinite Liveness Requirements, by Hélia Guerra and José Félix Costa,
*The Journal of Logic and Algebraic Programming*, 82(3-4): 137--161, Elsevier, April--May 2013. __Turing machines as clocks, rulers and randomizers__, by José Félix Costa.*Boletim da Sociedade Portuguesa de Matemática*, 67: 121--153, October 2012.- The impact of models of a physical oracle on computational power, by Edwin Beggs, José Félix Costa, and John V. Tucker.
*Mathematical Structures in Computer Science*22(5): 853--879, Cambridge University Press, 2012. - Axiomatising physical experiments as oracles to algorithms, by Edwin Beggs, José Félix Costa, and John V. Tucker,
*Philosophical Transactions of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences)*, 370(1971): 3359--3384, 2012. - Unifying science through computation: Reflections on computability and physics, by Edwin Beggs, José Félix Costa, and John V. Tucker. Olga Pombo, Juan Manuel Torres, John Symons, and S. Rahman (editors): Special Sciences and the Unity of Science, Chapter IV: 53--80. Book series:
*Logic, Epistemology, and the Unity of Science*, Vol. 24, Springer, 2012. __Comparing complexity classes relative to physical oracles__(short version), by Edwin Beggs, José Félix Costa, and John V. Tucker. Fernando Ferreira, Hélia Guerra, Elvira Mayordomo, and João Rasga (editors),*Programs, Proofs, Processes*, 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, June/July 2010, CMATI (Centre for Applied Mathematics and Information Technology), University of Azores, 2010, 62--72.- Limits to measurements in experiments governed by algorithms, by Edwin Beggs, José Félix Costa, and John V. Tucker.
*Mathematical Structures in Computer Science*20(06): 1019--1050, Cambridge University Press, 2010. - Computable scientists, uncomputable world, by José Félix Costa. Cristian S. Calude, Masami Hagiya, Kenichi Morita, Grzegorz Rozenberg, and Jon Timmis (Editors), Unconventional Computation,
*Lecture Notes in Computer Science*6079: 6--10, Springer-Verlag, 2010. - Physical oracles: the Turing machine and the Wheatstone bridge, by Edwin Beggs, José Félix Costa, and John V. Tucker.
*Studia Logica*, 95(1--2): 279--300, July 2010. - Computational Models of Measurement and Hempel's Axiomatization, by Edwin Beggs, José Félix Costa, and John V. Tucker.
*Book Chapter*, in Arturo Carsetti (editor):*Causality, Meaningful Complexity and Embodied Cognition*, Chapter IX: 155--184. Book series: Theory and Decision Library A, Vol. 46, Springer, 2010. - A foundation for real recursive function theory, by José Félix Costa, Bruno Loff, and Jerzy Mycka.
*Annals of Pure and Applied Logic*, 160(3): 255--288, 2009. - Computational complexity with experiments as oracles. II. Upper bounds, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker.
*Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences)*, 465(2105): 1453--1465, 2009. - Processes with local and global liveness requirements, by Hélia Guerra and José Félix Costa.
*The Journal of Logic and Algebraic Programming*, 78(3): 117--137, 2009. - Physical experiments as oracles, by Edwin Beggs, José Félix Costa, and John V. Tucker.
*Bulletin of the European Association for Theoretical Computer Science*97:137--151, February 2009. - Five views of hypercomputation, by Bruno Loff and José Félix Costa. Mike Stannett (editor): Future Trends in Hypercomputation,
*International Journal of Unconventional Computing*, 5(3--4): 193--207, Old City Publishing, Inc., 2009. - Differential equations, infinite limits and real recursive functions, by José Félix Costa, Bruno Loff, and Jerzy Mycka. M. Demiralp, W. B. Mikhael, A. A. Caballero, et al. (editors), Computational Methods and Applied Computing, Book Series: Mathematics and Computers in Science and Engineering, World Scientific and Engineering Academy and Society, 2008, 294-299. Article.
- Oracles and advice as measurements, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker. Cristian S. Calude et al. (editors), Unconventional Computation 2008, UC ' 08, Vienna, August 25--28,
*Lecture Notes in Computer Science*5204: 33--50, Springer, 2008. - Computational complexity with experiments as oracles, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker.
*Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences)*, 464: 2777--2801, October 8, 2008. - On the complexity of measurement in classical physics, by Edwin Beggs, José Félix Costa, Bruno Loff, and John V. Tucker. M. Agrawal, D. Du, Z. Duan, and A. Li (editors), Theory and Applications of Models of Computation, TAMC 2008, Xi'an, China, April 25--29, 2008,
*Lecture Notes in Computer Science*4978: 20--30, Springer, 2008. - The Euclid abstract machine, by Jerzy Mycka, José Félix Costa, and Francisco Coelho. Andrew Adamatzky and Susan Stepney (editors): Towards Theory of Unconventional Computing,
*International Journal of Unconventional Computing*, 4(3): 223--248, Old City Publishing, Inc., 2008. - The abstract immune system algorithm, by Daniel Pacheco and José Félix Costa. Selim G. Akl, Cristian S. Calude, Michael J. Dinneen, Grzegorz Rozenberg, and H. Todd Wareham (editors), Unconventional Computation 2007, UC ' 07, Kingston, August 13-17,
*Lecture Notes in Computer Science*4618: 137--149, Springer, 2007. Immune Lab. - Computability on reals, infinite limits and differential equations, by Bruno Loff, José Félix Costa, and Jerzy Mycka.
*Applied Mathematics and Computation*, 191(2): 353--371, Elsevier, 2007. - A new conceptual framework for analog computation, by Jerzy Mycka and José Félix Costa.
*Theoretical Computer Science*, 374(1--3): 277--290, Elsevier, 2007. - The P =/= NP conjecture in the context of real and complex analysis, by Jerzy Mycka and José Félix Costa.
*Journal of Complexity*, 22(2): 287--303, Elsevier, 2006. - Euclid abstract machine: the trisection of the angle and the halting problem, by Jerzy Mycka, Francisco Coelho, and José Félix Costa. Cristian S. Calude, Michael J. Dinneen, Gheorghe Paun, Grzegorz Rozenberg, and Susan Stepney (eds.), York, September 4-8,
*Lecture Notes in Computer Science*4135: 195--206, Springer, 2006. - Undecidability over continuous-time, by Jerzy Mycka and José Félix Costa. Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich (editors): Logics and Models of Computation: An International Logic and Computer Science Semester at Tel Aviv,
*Logic Journal of the IGPL*, 14(5): 649--658, Oxford University Press, 2006. - Real recursive functions and their hierarchy, by Jerzy Mycka and José Félix Costa.
*Journal of Complexity*, 20(6): 835--857, Elsevier, 2005. - The computational power of continuous dynamic systems, by Jerzy Mycka and José Félix Costa. Maurice Margenstern (editor),
*Machines, Computations, and Universality*, MCU 2004,*Lecture Notes in Computer Science*, 3354: 164--175, Springer-Verlag, 2004. - A compiler and simulator for partial recursive functions over neural networks, by João Neto, José Félix Costa, Paulo Carreira, and Miguel Rosa.
*Book Chapter*, Ahmad Lotfi and Jonathan M. Garibaldi (editors): Applications and Science in Soft Computing, Chapter VI: 39--46. Book series: Advances in Intelligent and Soft Computing, Vol. 24, Springer, 2004. - Analog computers and recursive functions over the reals, by Daniel Graça and José Félix Costa.
*Journal of Complexity*, 19(5): 644--664, 2003. __Symbolic processing in neural networks__, by João Pedro Neto, Hava T. Siegelmann, and José Félix Costa.*Journal of the Brazilian Computer Society*, 8(3): 58--70, 2003.- An analog characterization of the Grzegorczyk hierarchy, by Manuel Campagnolo, Cris Moore, and José Félix Costa.
*Journal of Complexity*, 18(4): 977--1000, 2002. - Canonical institutions of behaviour, by José Félix Costa and Hugo Lourenço. Maura Cerioli and Gianna Reggio (eds.),
*Lecture Notes in Computer Science*, 2267: 71--84, Springer-Verlag, 2001. - Verifying properties of neural nets, by Pedro Rodrigues, José Félix Costa, and Hava T. Siegelmann. J. Mira and A. Prieto (eds), IWANN'2001,
*Lecture Notes in Computer Science*, 2084:158--165, Springer-Verlag, 2001. - Iteration, inequalities, and differentiability in analog computers, by Manuel Campagnolo, Cris Moore, and José Félix Costa.
*Journal of Complexity*, 16(4): 642--660, 2000. - Book. Génese da Revolução Astronómica (The Astronomical Revolution) by José Félix Costa, Escolar Editora, 2000.
- Nonsequential automata semantics for a concurrent object-based language, by Paulo B. Meneses, Amílcar Sernadas, and José Félix Costa,
*Electronic Notes in Theoretical Computer Science*, 14(1): 245--273, 1998. - Mirror, mirror in my hand... a duality between specifications and models of process behaviour, by José Luiz Fiadeiro and José Félix Costa.
*Mathematical Structures in Computer Science*, 6(4): 353--373, 1996. - Refinement mapping for (discrete event) system theory, by Paulo B. Menezes, José Félix Costa, and A. Sernadas. F. Pichler, R. Moreno Díaz, and R. Albrecht (eds),
*Computer Aided System Technology, EUROCAST'95, Lecture Notes in Computer Science*, 1030:103--116, Springer-Verlag, 1996. - Architectural specifications: Modeling and structuring behavior through rules, by Carlos Paredes, José Luiz Fiadeiro, and José Félix Costa. H. Kilov and W. Harvey (eds),
*Object-oriented Behavioral Specifications*, Kluwer Academic Publishers, 1996, 221--240. - Synchronization in Petri nets, by Paulo B. Meneses and José Félix Costa.
*Fudamenta Informaticae*, 26: 11--22, 1996. - Object specification logic, by Amílcar Sernadas, Cristina Sernadas, and José Félix Costa.
*Journal of Logic and Computation*, 5(5): 603--630, 1995. - Institutions for behaviour specification, by José Luiz Fiadeiro and José Félix Costa. E. Astesiano, G. Reggio, and A. Tarlecki (eds),
*Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types -- Selected Papers, Lecture Notes in Computer Science*, 906: 273--289, Springer-Verlag, 1995. - Compositional reification of concurrent systems, by Paulo B. Meneses and José Félix Costa.
*Journal of the Brazilian Computer Society*, 2(1): 50--67, 1995. - Progress assumption in concurrent systems, by José Félix Costa and Amílcar Sernadas.
*Formal Aspects of Computing*, 7(1): 18--36, 1995. - Object inheritance beyond subtyping, by José Félix Costa, Amílcar Sernadas, and Cristina Sernadas.
*Acta Informatica*, 31(1): 5--26, 1994. - An institution of object behaviour, by Amílcar Sernadas, José Félix Costa, and Cristina Sernadas. H. Ehrig and F. Orejas (eds),
*Recent Trends in Data Type Specification: 9th Workshop on Specification of Abstract Data Types -- Selected Papers, Lecture Notes in Computer Science*, 785: 337--350, Springer-Verlag, 1994. - Data encapsulation and modularity: Three views of inheritance, by José Félix Costa, Amílcar Sernadas, and Cristina Sernadas. A. Borzyszkowski and S. Sokolowski (eds),
*Mathematical Foundations of Computer Science 93*,*Lecture Notes in Computer Science*, 711: 382--391. Springer-Verlag, 1993. - Espelho, espelho meu... , by José Luiz Fiadeiro and José Félix Costa, Actas do III Encontro de Algebristas Portugueses, 71--86, Universidade de Coimbra, 1993.
- Process semantics of temporal logic specification, by José Luiz Fiadeiro, José Félix Costa, Amílcar Sernadas, and Tom Maibaum. M. Bidoit and C. Choppy (eds),
*Recent Trends in Data Type Specification: 8th Workshop on Specification of Abstract Data Types -- Selected Papers, Lecture Notes in Computer Science*, 655: 236--253, Springer-Verlag, 1993. - Object interaction, by José Félix Costa, Amílcar Sernadas, Cristina Sernadas, and Hans-Dieter Ehrich. I. Havel and V. Koubek (eds),
*Mathematical Foundations of Computer Science 92*,*Lecture Notes in Computer Science*, 629: 200--208, Springer-Verlag, 1992. - A categorial framework of process interconnection, by José Félix Costa and Amílcar Sernadas.
*The INESC Journal of Research and Development*, 4(1):81--93, 1993. - From processes to objects, by Amílcar Sernadas, Hans-Dieter Ehrich, and José Félix Costa.
*The INESC Journal of Research and Development*, 1(1):7--27, 1990.

- Cristian S. Calude, José Félix Costa, and Hélia Guerra, (guest) editors of a Special Issue of Applied Mathematics and Computation, (219)1, September 15, 2012, Elsevier, Towards a computational interpretation of physical theories, online.
- José Félix Costa and Nachum Dershowitz, (guest) editors of a Special Issue of Natural Computing, Springer, on Unconventional Computation (UC 2009), 10(4), December 2011, online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of International Journal of Unconventional Computing, 7(5), September/October 2011, Old City Publishing Science Journals, Special Issue on Physics and Computation (P&C 2010), online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of Natural Computing 9(4), December 2010, Springer, Unconventional Computation (UC 2008), online.
- Cristian S. Calude, José Félix Costa, Nachum Dershowitz, Elisabete Freire, and Grzegorz Rozenberg editors of Lecture Notes in Computer Science, volume 5715, Unconventional Computation 8th International Conference, UC 2009, Ponta Delgada, Azores, Portugal, September 7--11, 2009, Proceedings, Springer, online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of Natural Computing, 8(3), September 2009, Springer, on Physics and Computation, online.
- Cristian S. Calude and José Félix Costa, (guest) editors of a Special Issue of Applied Mathematics and Computation, 215(4), October 15, 2009, Elsevier, Physics and Computation, online.
- Cristian S. Calude, José Félix Costa, Rudolf Freund, Marion Oswald, and Grzegorz Rozenberg editors of Lecture Notes in Computer Science, volume 5204, Unconventional Computation 7th International Conference, UC 2008, Vienna, Austria, August 25--28, 2008, Proceedings, Springer, online.
- José Félix Costa and Francisco Dória, (guest) editors of a Special Issue of Applied Mathematics and Computation, 178(1), July 1, 2006, Elsevier, on Hypercomputation, online.

- Program committee member of the 13th International Conference on Unconventional Computation & Natural Computation, UCNC 2014, University of Western Ontario, London, Ontario, Canada, July 14-18, 2014.
- Co-organizer (together with Valentina Harizanov) of the Session «Computability» of the Logic Colloquium 2013, Évora (Portugal), July 22--27, 2013.
- Program Commitee member of the Conference Unconventional Computation & Natural Computing 2013, Milano (Italy), July 1--5, 2013.
- Program Commitee member of the 2013 Symposium for Computing & Philosophy, University of Exeter (U.K.), April 2--5, 2013.
- Program committee member of the Conference Unconventional Computation & Natural Computing 2012, LIFO, University of Orléans (France), 3--7 September, 2012.
- Invited Speaker, Workshop Physics and Computation, Institut Henri Poincaré, 28--30 June, 2012.
- Invited Speaker, Workshop The Incomputable, Kavli Royal Society International Centre, Chicheley Hall, 12--15 June, 2012.
- Program Commitee member of the International Workshop on Theoretical Computer Science Dedicated to Professor Cristian S. Calude's 60th Birthday, Auckland, New Zealand, 21--24 Feb 2012.
- Member of the program committee of the 9th International Conference on Unconventional Computation UC 2011, FUNDIM laboratory of the Mathematics Department, University of Turku, Finland, June 6--10, 2011.
- I organized with Cristian Calude, Walid Gomaa, Hélia Guerra, and Karl Svozil the Third International Workshop on Physics and Computation 2010, Egypt, August 30 -- September 4, 2010.
- Member of the program committee of the ICALP 2010, 37th International Colloquium on Automata, Languages and Programming, July 5--12, 2010.
- Invited Speaker at the 9th International Conference on Unconventional Computation, UC 2010, Tokyo, June 21--25, 2010.
- General chair of the 8th International Conference on Unconventional Computation, UC 2009, Ponta Delgada, September 7--11, 2009.
- Invited speaker at the Workshop Complexity Resources in Physical Computation, Oxford University Computing Laboratory, Oxford, UK, August 24--26, 2009.
- Invited speaker at the Conference SPUC09, The Science and Philosophy of Unconventional Computing, Cambridge, UK, March 23--25, 2009.
- I organized with Cristian Calude the Workshop on Physics and Computation 2008, a satellitte event of the 7th International Conference on Unconventional Computation, UC 2008, Vienna, August 25--28, 2008.
- Co-chair of the program committee of the 7th International Conference on Unconventional Computation, UC 2008, Vienna, August 25--28, 2008.
- Invited speaker at the International Colloquium on Causality, Meaningful Complexity and Knowledge Construction, University of Rome "Tor Vergata", Rome, June 5--7, 2008.
- Invited speaker at the Conference TAMC 2008, 5th Annual Conference on Theory and Applications of Models of Computation, Xi ' an, China, April 25--29, 2008.
- Invited speaker at the BCTCS on Physics and computation: An essay on the unity of science through computability, April 7--10, 2008.
- Member of the program committee of the 6th International Conference on Unconventional Computation UC 2007, Queen's University, Kingston, Ontario, August 13--17, 2007.
- Invited speaker at a Special Session of the European CiE Conference Computability in Europe 2007: Computation and Logic in the Real World, University of Siena, Siena, June 18--23, 2007.
- Invited speaker at the Workshop Future Trends in Hypercomputation, Sheffield, UK, September 11--13, 2006.
- Lecturer at the International Logic and Computer Science Semester at Tel-Aviv (Tel Aviv University), March 10 -- 12, 2004.