A deterministic connectionist machine for solving the traveling salesman problem (TSP) is proposed. The original TSP is reformulated as a penalty problem, i.e., an unconstrained nonlinear programming problem with penalty terms. A deterministic connectionist machine is designed to realize the solution procedure for the penalty problem. The major feature of the machine is that the penalty parameter increases as the states evolve, so the generated tours are always valid. The stability of state trajectories and feasibility of the generated solutions for the proposed connectionist machine are theoretically and practically justified. A simulation algorithm is presented, and numerical simulations results are reported. They show that the motion of the state is always asymptotically stable, the generated tours are always valid and near-optimal if not optimal, and the solution procedure is fairly robust to the selection of the step length, initial state, and initial penalty parameter.