INTRODUÇÃO: Desde 2006, quando Jeannette Wing popularizou o termo “Computational Thinking” como sendo uma habilidade essencial para as pessoas do século XXI, há um grande interesse da comunidade científica e de governos de diversos países pela exploração do Pensamento Computacional na Educação Básica. Muito embora Wing tenha descrito o Pensamento Computacional como um processo de resolução de problemas que se baseia nos limites da computação, e que mais fundamentalmente aborda a questão “O que é computável?”, pouca atenção tem sido dada a este questionamento na prática. OBJETIVOS: O principal objetivo deste estudo foi apresentar uma reflexão teórica sobre a importância da noção de computabilidade para o Pensamento Computacional, bem como apresentar o projeto de um jogo para a sua introdução na Educação Básica. MÉTODOS: Através do procedimento metodológico da pesquisa bibliográfica, foi realizado um estudo sobre os temas Pensamento Computacional, Teoria da Computação e tecnologias utilizadas na exploração do Pensamento Computacional. RESULTADOS: Com bases nos estudos realizados, foi elaborado o projeto de um jogo de lógica inspirado em modelos computacionais. CONCLUSÃO: Entende-se que o jogo proposto neste artigo pode representar uma nova estratégia para a exploração do Pensamento Computacional na Educação Básica, pois além de trazer noções de computabilidade à tona, conduz a uma forma de pensar baseada em trocas de estados, que representa um modelo adequado do funcionamento do cérebro consciente.