functional vs state-based As mentioned in Lambda Calculus - Computerphile, 


  Alonzo Church's method is functional where a function as a blackbox,
  takes an input, processes, and produces an output, and Turing machines
  have internal state.



First, I would like to know what does it exactly mean by functional and state-based?
Are they the same as the terms stateful and stateless? 
And how are they related, similar and different from one another? 


Not quite sure if this question is to be asked here or in Stackoverflow.

Ref: https://www.revolvy.com/main/index.php?s=State+(computer+science) 
Ref: Learning fundamental differences between functional programming and Object Oriented Programming
The terminology isn't absolute when applied to actual languages. Usually "stateful" refers to holding the "state of the computation" largely in variables of some sort (variables = changeable references to values). These can be ordinary variables (C) or fields of objects (C++, Java). It is possible in many such languages, however, to minimize such state and to program largely with constants only and with parameters of functions and methods. The latter can be variables or constants, depending on the language. 

The reason that stateful languages can be programmed this way is that they also employ a run time stack in which values can be maintained. 

Stateless programming in most commonly done in functional languages that minimize the use of variables, depending on constants and constant function arguments. The computation "state" is the stack itself. However, most functional languages do have some mechanism for declaring variables (things which vary), though they also tend to call names that refer to constants as "variables" confusing the issue somewhat. 

In "pure functional programming" you utilize only constants and immutable function arguments to move values around the computation. The "State of the Computation" is the state of the run time stack. This is true Stateless programming. 

Most imperative and OO programming, on the other hand is stateful. The "State of the Computation" is comprised of both the state of the run time stack and the currently referenced values of the variables. 

Another way to think of it is that in stateless programming, the state is "implicit" in the stack and the current program pointer. In stateful programming, the state is explicit in the variables and fields (to a large part - there is also the stack).