0
$\begingroup$

From this answer, and the comments that follow:

To clarify, this machine T′ with the fixed output for all inputs is a Turing machine? – Shashank V M

@ShashankVM, Yes, T′ is a Turing machine. – D.W.♦ (When can a deterministic finite-state-automata (DFSA) along with its input sequence be said to be a part of another DFSA?)

From what I understand, a machine with fixed output for all inputs is a Turing machine.

Consider this thought experiment, I have a "machine" which is a wall with a slit through which I can pass a tape in. The "output" of this machine is on the wall, i.e. it is painted on the wall as a fixed string $S$, which for the purpose of this experiment is "Hello". So no matter what is written on the tape, the output of this "machine" is "Hello". From what I understand this "machine" is a Turing machine.

Is my understanding correct or am I missing something?

Because I find it hard to believe that this wall with a slit can be considered a Turing machine, when a supercomputer is considered a Deterministic Finite State Automaton.

Also I cannot see how this "machine" can emulate any another Turing machine or do any useful computation.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

There are many different Turing machines. Each one runs a fixed, hardwired program. Most Turing machines do nothing useful; many of them just halt immediately.

Some are universal, meaning that they can emulate any other Turing machine given a description of its hardwired program as part of their input, but most aren't. The machine that always prints "Hello" obviously isn't universal, but it is a Turing machine.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh, I had forgotten that a universal turing machine is different from a turing machine. $\endgroup$
    – Shashank V M
    Mar 1, 2021 at 7:02
3
$\begingroup$

There's no notion of "can be considered to be a Turing machine". Something either is a Turing machine, or it isn't. There's a formal mathematical definition of what a Turing machine is: https://en.wikipedia.org/wiki/Turing_machine#Formal_definition

I never claimed that just because some process always produces the same output, that process must be a Turing machine.

There might be some confusion about Turing machines vs DFAs. A computer could be modelled as a DFA (if we treat its memory size as fixed), or it could be modelled as a Turing machine (if we imagine that it's possible to gain more memory; or we just don't care to make use of the fact that memory size is fixed). These two different ways to think about a computer have different advantages and disadvantages. I suggest reading Is a PDA as powerful as a CPU? and How many gates until Turing Complete and How does an automaton model a computer or something else? and How does an automaton actually "compute"?, as I suspect they get at the core issue you are struggling with.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you suggest a good textbook to study these topics? $\endgroup$
    – Shashank V M
    Mar 1, 2021 at 7:00
  • 1
    $\begingroup$ @ShashankVM, Sipser is one standard textbook: math.mit.edu/~sipser/book.html $\endgroup$
    – D.W. ♦
    Mar 1, 2021 at 7:02
  • $\begingroup$ Thanks for this. $\endgroup$
    – Shashank V M
    Mar 1, 2021 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.